definitely replace the heatsink and fan. the cooler master Evo hyper 212 EVO is a great low cost cooler if you have the room in your case (should be ok in most mid towers)
as for whether to replace the CPU... what is the model number of your motherboard. I wouldn't recommend replacing the cpu and mobo unless you are finding yourself lacking in performance in stuff that you actually use your computer for. I wouldn't upgrade the cpu just because of temps.