Can stove grates be repainted?
You will need to use something other than your box store hi temp paints if you want really good results. They are more like Hi-temp Coatings than they are paints. Before Painting you will need to do a really thorough cleaning of them. Your preparation work is the HARDEST PART and the MOST important part of a good durable paint job. Anybody can squeeze a spray can - the prep work makes all the difference.  Take your time in the cleaning and PREP and you will have results as good as or better than a 'professional'.
A couple suggestions I have for you is to purchase something meant for hi-temperatures 500 to 1500 degrees
http://www.stovepaint.com/ .. although this says their paint is not for cooking surfaces or direct flame contact.
https://www.kbs-coatings.com/XTC.html