Use paste. Pads can be a mess to remove, if ever necessary. For a locked processor, you don't need to worry about finding the absolutely best paste in the world; an old standby like AS-5 would be my choice. The only ones that aren't that great are the white silicon grease. Any silver-based (gray) paste will be fine.
Edit: Oh, and yes, most HSF's come with paste.