Is removing the paste and re applying the only way to fix this? I have no idea how to perform that procedure..
This is why I would recommend not doing this procedure. If you dont know what you are dont know what you are doing you could:
Ruin a possibly perfectly good GPU
Void the warranty in the process.
If the paste is bad, RMA the card. If the fan bearing is bad as I suggest...RMA the card.