The purpose of thermal paste is to ensure the surface of the heatsink and the heat spreader are making as complete a contact as possible. In the manufacturing process, microscopic gaps will be present which will allow air to be trapped between the surfaces. Air doesn't conduct heat very well, so thermal paste is used as a filler.
(Image and further reading here)
Thermal paste is not as good a conductor as metal to metal. As such, you should be careful not to use too much, it shouldn't be too much that it prevents a good metal-to-metal contact. Applying new thermal paste can help temperatures as over time it may settle differently or crack, creating gaps again. It won't magically cool better though, but may be more efficient at heat transfer.
Your temperatures aren't too excessive. In my experience, AMD processors run a bit hotter in general, but either way these temperatures are not critical. Remember to take into account ambient temperature in the room as well, as a standard fan and heatsink will not be able to dramatically lower the temperature of the CPU with a higher ambient temperature.
Ensure the airflow is sufficient, that you aren't using excessive thermal paste, that the temperature of the room isn't too warm and that the machine can get a good supply of cool air and it's not just recycling its own hot air (in the case of a laptop, consider a cooling mat under it with fans to draw cool air towards the machine).