I have the 3450 and I never go above 61 on gaming on the stock cooler. I think depending on your ambient temps and case airflow setup, those temps are fine. I think within gaming anything above 70 might be odd, but even then u are probably still ok.
check case airflow and cable management, and make sure you fully clicked the cpu cooler in place.
yes replacing the thermal paste may help with a few degrees, but worth checking for good airflow etc first.