If you are going to do it, you may as well do it properly the first time around.
I ended up doing it and it was a lot easier than I originally thought. The paste just came off super easy and the CPU stock fan has the thermal already applied. Made a world of difference to the PC. I am tempted to buy an additional 3 fans now though, so I can mount one on the bottom and two at the top. Would these fans need to pull air in or push air out?