Your temps aren't bad. New paste, the best latest brand would give you better cooling.
How much? Maybe 1-2 C, and thats a HUGE maybe. Buy some quality Tpaste, enough for 2-4 uses and call it a day.
What to buy? OMG, that question can run in circles in fourms for years. I recommend MX-2. Popular, easy to apply, and I like it.
Ohh We have no idea what processor, effective case cooling setup, ambient temps you have. So 61C might be great, might be terrible. In fact the 59C to 61C swing your seeing could be your room is warmer.