Some people do lap [http://www.overclockersclub.com/guides/lapping/] their CPUs and heatsinks, but it's only worth it for extreme overclockers who're willing to endure (and able to reduce) the possibility of serious damage to their equipment to do so.
Even though the old paste is gone, you should carefully clean the surface with a small amount of high-purity alcohol and a lint-free cloth to remove any small bits of residue. Give it a few minutes to evaporate completely before applying the TIM.
For normal application, a small dot in the center of the CPU will do it. Some people prefer to spread a very thin layer on with a toothpick, latex glove, or finger in a plastic bag to ensure even coverage. The idea is to spread the thinnest possible layer, which will fill in tiny imperfections in the metal surfaces. Mount the heatsink straight down and secure it normally.