So today I bought a new heat sink for my CPU, and the heat sink came with thermal paste on, should I still reapply thermal paste on my CPU regardless of the paste that's on the new heat sink?
Mr K is right. If you ever take the heat sink off again for any reason, clean the old stuff off with propyl alcohol, get thermal paste with the highest thermal conductivity available to you 2.5-5 is just fine and apply a small amount in the centre (about a pea size glob for 1150-1155 socket and a tiny bit more if it's a bigger chip like a socket 2011) and don't smear it. Let the heat sink spread it and you'll avoid getting air pockets.