If you are running the latest version of Prime95 the temps are fine. Some people don't recommend the latest version of Prime95 on the new Intel chips. I still use it, but you have to remember it will get the chip far hotter than any other load you can place it under.
Yes a nicer thermal paste would help, but really not enough to make a huge difference. The stock cooler is OK, but if you really want to drop your temps you need a new cooler.