Nice results! Any heavy bodied acrylic paint is supposed to work well with engraved stone/tile. Those might be easier to clean up any stray splotches.
There are also wax/pigment combinations readily available. "Rub N Buff" is a popular one I've tried....cool metallic colors! It sometimes dries VERY quickly and sticks amazingly well (so clean up can be a bit more work).
I suggest for any of these that instead of rubbing a soft cloth (paper towel, etc) over the stone, put the cloth on a flat surface and rub the stone/tile on the cloth. That will minimize how often the solvent-laced soft cloth will get pushed into the engraving and remove some of the color effect.
Lowes sells 12" x 12" tiles, a half inch thick, of polished black marble that engraves reasonably well and really pops when you put gold metallic fill into the engraving! I expect the copper and bronze fills would also look pretty cool.
I'm hoping to get some laser time Tuesday to do some accuracy tests. The things I've cut so far where size matters have been off by a non-trivial amount. I set up a test file with some exact sizes that I'll engrave or cut then measure. The error could be in the drawing program or could be in the laser itself. If it's consistent, we can account for it in any design where it matters...