Thermal paste will give better thermal transfer between two objects. Rarely are objects flat, this means that only a fraction of the area is being used for heat transfer. And heat transfer depends on the area and the material (thermal grease has a much higher thermal conductivity than air). So use thermal grease or a thermal pad for best results.
Thermal pads usually have a lower thermal conductivity and conduct heat less. Almost any kind of metal will increase the thermal dissipation to air.
A good idea would be to calculate the heat that needs to be dissipated in the first place. Take the voltage drop of the regulator and multiply it by the current and that should give you the thermal dissipation number.