I'm not sure about the paint part, we don't ever paint our dishes, but those in my domain is normally covered by a radome cover.
As for rust - if the surface isn't smooth it can affect your signal. Think of your dish as a mirror which reflects all the light back to the horn feed. If a mirror isn't smooth, the light scatters and the reflection becomes blurry. Same with microwave - if the dish isn't smooth, the microwave scatters. Non linearities can do funny things to a signal.
If your dish is starting to rust, I'd recommend that you do paint it to prevent further rust. I wouldn't apply too much paint - as liquids can also attenuate a signal (make it weaker).
If you experience signal issues, make sure that your dish is properly panned (looking in the right direction) before going to buy a new dish. I don't know what mechanism your system will use, but most systems provide some means of getting the signal strength without having to watch on the TV. You'd normally make the dish look a bit to the left of where you think the satellite is, and then move it to the right. The signal should increase as you get closer to the right point, and then start decreasing as you move past. Once that happens, just go back to the left a bit. Repeat the process for the vertical. Always pan horizontal and vertical separately.