You can buy thermal paste only if you feel it necessary and depending on the cooler you buy. Some coolers will come with good quality thermal paste while others will be poor quality.
One thing to mention is to make sure you clean the CPU properly when installing a new cooler. You can use lots of cleaning fluids but anything that is alcohol based works well (including nail varnish remover). You can also use one of the cleaning kits/fluids available such as the
Arctic Silver kit (which I use. Does a good job) or
Akasa cleaner.
A fan that I'd recommend due to it's size and the fact that it's on clearance (CHEAP) is this:
YOUR BASKET
1 x
**B Grade** Thermalright HR-02 Macho CPU Cooler (Socket LGA775/LGA1156/LGA1155/LGA1366) £21
Total : £21.00 (includes shipping : FREE).
Should do a good job. Although I would drop OcUK a message asking them what parts are missing as you don't want one turning up without the 1155 mounting brackets. B grade products can sometimes have parts missing which is why you should ask beforehand.