Thermodinamically speaking, I don't think the difference between the temperatures is a good parameter to measure the efficiency of the heatsink (and thermal paste) because temp exchange between cpu and heat sink is by conduction while heat sink x ambient is by convection. These are 2 different processes with different speeds and variables.
If you have a very big difference between both, this can only prove that your cooling is very efficient and that conduction between cpu and heat sink will be improved because it's driven by the temp difference of the surfaces in contact. If the diffence is too small, conduction will be low and your cooling is not sufficient. None of the cases mean your thermal paste is not good anymore.
The only thing that will say you need to check the thermal paste is when there is a reasonable (or big) difference (effective cooling) and the CPU temp still increase.