I also removed the heatsink and cleaned it from all the dust and renewed the thermal paste but nothing changed.
Did you place a very light coating on.....less is more.
About the size of a rice grain or rolled oat (as in oatmeal) is plenty.
To ensure proper spread, simply take a piece of plastic wrap, such as Saran Wrap or similar brand, wrap it around your finger, place the amount above in the center of the CPU, gently spread the paste over the entire surface, just enough to coat the surface, This way you physically see how the paste is spread. Many will place a drop in the middle of the CPU, install/reinstall the fan/heatsink & hope for the best. If this is done with 100% precision, no tilt of the heatsink while replacing, all may very well be fine.
However, all it takes is a small tilt in any direction when seating, a very small one, the paste will spread wrong, may push more to one side, or if the heatsink itself is off center at all, including the clamp pressure, the paste will be uneven, with portions having none. Many times these will simply run at higher temps than normal, other times there will be shutdowns (BSOD's) to save your chip, in extreme instances the chip will be shot.
As to the CPU fan, if you've been running the same one all these years, as Louis points out above, a new fan is likely needed. You can likely find a brand new, unused one for your model from an eBay seller (check reputation & feedback before purchase), you have both eBay & PayPal protection on the transaction. There was a couple of other times I found this component on the Amazon site & everything was perfect (again, check seller reputation).
Or go to a site such as Newegg & get an upgraded one for your model. Some or most of these will require the MB to be removed for the backplate, so if what you want is less work, try to find an OEM one. Depending on model, the fan & heatsink may be one uint, others will be fan only. To be honest, I have more experience with Intel than AMD components of this nature, have only replaced a couple on AMD units, along with the CPU itself.
Here are two new CPU Fan/Heatsink for your model (by the same seller), this is 2-3x that of the CPU alone, of which many are being sold for as little as $9.00. This is how I find many components for repairing computers at low cost.
Seller has excellent track record & I always review this before making purchase.