All the stuff you need should come with a decent brand, low cost cooler, and yes, you must remove and re-apply thermal paste. There are lots of written and video guides on the net on cooler installation ... google is your friend
Good luck! ... you really will be much happier with a new cooler. Small fans by their nature are louder than larger fans because they have to spin faster to move the same amount of air over a heatsink surface, even if they claim to be "silent". 70mm is an odd fan size to find and replace too.