Try dusting it out first. If you have a flashlight try shining it through the radiator with the pc turned off, there's probably dust built up in there between the fan and the radiator fins. Use something like compressed air to blow the dust out.
There are a variety of decent thermal pastes out there, arctic mx4, shin etsu, prolimatech pk1, noctua nt-h1. This is an inexpensive tube of decent thermal paste, same stuff I'm currently using.
http://pcpartpicker.com/product/48fp99/prolimatech-thermal-paste-propk115g
Something like this for dusting out your pc. Doesn't have to be this brand, your local stores probably have something similar in the electronics department.
https://www.amazon.com/Dust-Off-Compressed-Duster-Pack-DSXLP/dp/B003551HN6/ref=sr_1_71?s=pc&ie=UTF8&qid=1480501073&sr=1-71
If looking to clean off the thermal paste and you don't have any isopropyl rubbing alcohol consider picking some up. A bottle is usually only a dollar or two, try to find 91% or higher. Used with a lint free cloth it works well, cleans the metal lid on the cpu and the cooler base without leaving any residue and it evaporates pretty quickly.
You mentioned only one fan, the cooler fan. Is that your only case fan? What pc case are you using? If that's your only case fan then it might be worth looking at your case for fan mounts in the front to see if a fan can be installed there. At minimum a case should have an intake fan and exhaust fan, even if the aio radiator fan is doubling as the exhaust fan. Without decent airflow through the case everything is going to run hotter, the cpu, gpu, motherboard components like the vrm (voltage regulators to the cpu). If any of those things are heating up more than normal it could be causing problems.