Have you checked to see if the heatsink is plugged with dust as well? Laptops typically have a small heatsink right where the air exits the fan. You'll probably have to pull the fan out to check it. They'll get a big ball of dust on the inside portion of the heatsink that isn't always obvious just looking at it.
If you end up reapplying thermal paste, it's not that difficult. Static has a potential to be problematic, but realistically, modern components are quite robust. I've been less than careful with a lot of my parts in the past and have never fried a board or component from static electricity.
Best place to work on it is on a dining room table. Before you sit down and work on it, touch some metal to discharge yourself if you are concerned about static.
If you find the heatsink isn't plugged up, or you get to the point you are going to reapply thermal paste, come back and let us know beforehand as there are a few pictures and details we can give that'll help out.
As for thermal paste typically most of the brand name ones will be sufficient, however cooling in laptops is less than optimal. If you are going to go through the trouble of reapplying new paste, it wouldn't be a bad idea to go ahead and get a highly rated paste. The worst you''d be is out $12-$15 vs $5 for a cheaper alternative.
Whichever paste you get though, avoid any of the metal based pastes. They are at the top in terms of performance, but they are difficult to work with, they are conductive and can NOT be used on aluminum.
The top two rated conventional pastes according to http://overclocking.guide/thermal-paste-roundup-2015-47-products-tested-with-air-cooling-and-liquid-nitrogen-ln2/12/ are Thermal Grizzly Kryonaut and Gelid GC-Extreme.
I personally have the Gelid and am quite happy with it. The Gelid is a bit thicker in consistency than some of the cheaper pastes, but I used a hair dryer to warm the paste, CPU and heatblock before applying and it was no worse than using any other paste.
Edited by Ram4x4, 17 February 2016 - 08:33 AM.