Hi. Wouldn´t use paste as such, but thermal tape. I once fitted a tri-fan on an EVGA GTX 260, got some thermal tape for that. When peeling off the heatsink you´ll probably encounter some plastic like material that is easily removed, and it´s rather thick, when compared to how thin you spread the paste onto the cpu. It may be, that the heatsink doesn´t make proper contact if you only apply a thin layer of paste. I replaced the material with an almost gel-like tape, that I spread across all the components, the uniform thickness of the tape ensures proper contact with the heatsink. You may want to look into additional cooling of components, I found that the heatsink didn´t cool certain elements that would benefit from cooling. So I went and got small single heatsink elements, but ended up using thermal glue, to make them stick. Don´t rely on the preapplied adhesive. They go upside down when you fit the card, and you hate to hear that tiny "clunk" of a piece of metal falling off your board...
But the GTX 260 is a long time ago, things may be different now. But, open it up carefully, take a look. And don´t throw away the factory applied contact material right away, the impressions on it tell you which components need the contact, can get confusing when you look at a lot of small surfaces in different levels. I´d photo document the progress, the pic.s might help if you´re in doubt about what finally goes where.
I also used the tape for my old Striker II mobo to put on the MOSFETS after tinkering with the heatpipes. Good stuff.

Let us know how you progress, you could post some pictures 😉

Bjorn