No, as long as the heatsink is correctly inserted there should be enough contact as not to immediately overheat the processor, thermal paste improves contact between the heatsink and processor, it's not required, but for best effectiveness it's definitely a good idea.
At full load it could mean a different from 3c to 10c + .
No, it pretty much is required. All heatsinks and CPU surfaces have micro fractures that will have air, and serve as an insulator preventing heat transfer.
Thermal paste if not required if you're able to sand down the surfaces so they can form a tight vacuum fit...which is nigh impossible without special equipment.