When you notice a rise in average temperatures.
90% of the time you can leave paste on between major overhauls.
What paste is down to what you want to pay. Most thermal compounds perform within a few degree C of each other, so it isn't vital to get the best paste out there unless you are doing heavy overclocking.
Arctic MX-4 is my go to recommendation for a decently priced and versatile compound. Works well on all types of interfaces.
For a smooth chill plate and CPU interface, you will find that the thinner, more liquid pastes work better. (See thermal grizzly, noctua)
For rougher direct heat pipe coolers you often want a thicker paste. MX-4 works well here.