I would do both.
I'd remove it and clean both surfaces with isopropyl alcohol or equivalent. I'd then dry fit the Kraken before the actual mounting to be sure the fitment is good. If not, consult the manual or call the manufacturer and get their suggestions. When remounting it, ensure that it is set up for your particular CPU socket (it sounds like it is configurable for different sockets).
There are many methods to apply thermal paste. Apply a pea sized drop to both the CPU and the Kraken, and use some type of spreader (I'd carefully use a razor blade, but even a piece of cardboard would work in a pinch, I'd imagine) to lightly coat both surfaces. Less is more; you just want enough to fill any minute imperfections and provide a good seal between the two surfaces. Ensure that the Kraken is mounted so that the 2 surfaces are tight together.
Here's a link to Tom's thermal paste reviews:
http://www.tomshardware.com/forum/274824-29-thermal-compound-roundup-2011 . Arctic Cooling MX4 seems to be well liked, and a good performer.