Yes you can paint them with high heat BBQ grill paint. You can find this paint at any hardware store, walmart or lowes etc. It is rated for 1400 degrees normally. Be aware, however, that the surface in contact with your pans will wear off fairly quickly. I personally would paint the grates, then burnish the paint off where it makes contact with the pans so the paint doesn't transfer onto the pans.
The other way to renew the grates is to sand off any rust etc, then season them with vegetable oil in your oven. This is the same technique as one would use for a griddle. They will not be jet black, but will be rust free and look like a professional range top.