It doesn't take much heat to fry an egg. Most shovels are made of a mild steel, aiming toward toughness rather than edge-holding ability. They are tempered, but brief exposure to heat shouldn't have a significant impact.

I use hardware-store spades to manage the fire and coals in my firepit. I've never noticed a problem (I sharpen the front edge for digging/chopping plant material in my garden and yard, so I'd notice). But the steel is only exposed to heat for a few moments -- it doesn't sit in the coals and glow red.

I don't think I would try to cook with one of my Cold Steel shovels though. The temper on those is key to their multi-functionality. And the paint would likely add some spice of its own (bleah).