these cards get hot. I've got two 4870's, and they can reach 90C in some situations. They are made that way, so it's not an issue to be scared of. They will throttle themselves, and adjust their cooling when necessary. clock those devil until you start having artifacts, then back off just a little.
The FPS thing is normal, unless the test is repeatedly doing the same tasks, the FPS will vary, just as they do in games. If you list all of your hardware specs, we can help you more, but in general overclocking the CPU can help; it depends mainly on the cpu you have, and what screen resolution you are playing at.
artifacts are little parts of the screen that look different. You may have pink or green squares that show up and dance across the screen, textures that flicker, blinking black screen, ect.. These aren't signs of damage, just signs that you need to back off some.
Well, it really just depends. I have the 4870, which I would call the big brother of your card. However, they should OC proportionally I would think. I have my cards overclock to 790 MHz on the core clock, and 1050 MHz on the memory. Any higher and I get artifacts.
This correlates to about a 5.33% OC on the core clock, and about a 16.7% OC on the memory. If you do the same, multiply your core clock by 1.05, and your memory clock by 116 and you should have a good starting point.
There are several good guides to overclocking cpu's. Google them for a few hours before you start.