Whenever you are painting something high-temp, ALL the coating must be high-temp-rated. More than that, a grill must be food-rated - you don't want it off-gassing stuff that will poison your steaks!
The way rust CONVERTERs work is they have a chemical reaction that turns rust into a supposedly inert compound, and then, this stays under the paint permanently as a "primer". In my experience that trick works for about a year, then it blooms even worse. And that isn't even on a grill, where the heat and condensation will greatly accelerate that! So I refuse to use rust converters except on things that will live indoors going forward. And as said, this stuff is not high-temp rated.
They make rust removers where they do the same chemical reaction (basically: phosphoric acid) to remove the rust, but then, the magic juice washes away so you are painting bare metal.
By the way, when using any anti-rust chemical, it's best to use physical removal to get rid of any rust possible - that way the chemical isn't wasting its limited energy dissolving rust that's already separated.
The most reliable way to remove rust and get to bare metal for painting is to media blast. NASA has done a lot of work on this, because somebody (Nikita Khrushchev?) placed the Kennedy Space Center right on the beach in Florida, basically corrosion hell, and they have millions of tons of nationally important steel latticework there. Naturally, they science'd the heck out of it, and they have a whole website on that at http://corrosion.ksc.nasa.gov ...
Primers make a huge difference, but there is no good answer for primers on hot metal. Even galvanizing, the activity in a grill will melt the zinc, and you do not want zinc vapor on your food! When we have to hot-work galvanized, we drink milk afterward to help our body attach and dispose of the toxins.
Really your best bet is simply to prep the metal as much as possible, and use grill paint as directed.
As far as how to stop it rusting again, don't leave your toys outside lol.