Your temps are not really out of line for that processor, although maybe a little warmer than I like in the rigs I build. A front and rear fan should take care of your heat and yes, if you clean off the old thermal paste and install new (properly), then it might help you. Use only Artic Silver for the past and follow these directions:
Applying Artic Silver Thermal Paste