Just because the CPU can reach such high temperatures doesn't mean that you don't have a problem with the CPU that the paste shouldn't fix. There is really no reason why the temp should be that high.
Make sure that you wipe the paste completely. Watch a youtube video for that. It is easy. Buy a market cooler also. I recommend you to buy a Cryorig h7 or Cooler master hyper 212 evo or a Thermaltake frio silent 14.