You may need a replacement retainer .

Look at the top of the heatsink. There you will see 2 levers. Flip those in the opposite direction. Try lifting the heatsink as straight up as possible. As you never know if the cpu still is'nt glued to the heatsink plate. You dont wanna bend or brake those pins on the cpu.

When you have removed the heatsink. look at the socket. There you will see another lever. This lever locks the cpu in the socket ( hopefully). Just raise this, and take out the old cpu.

If you now, look into the socket. You will find that there is a marking in one of the corners.
You have a corresponding marking on the cpu. This shows in wich way the cpu should go into the socket. See pictures.

You should always replace the paste / pad. Paste is better than a pad.

Remove the paste from the heatsink plate, using oil free Acetone or Isoprophyl alcohol and a lint free cloth. Or remove the pad, and clean afterwards with some of the fluids above.

When you apply the new paste. Just apply it in the size of a big rice grain in the centre of the cpu.
The heatsink pressure will take care of spreading it for you.

Do not forget to connect the cpu fan!!!

And dont forget to remove yourself from static electrisity, by grabbing a water tap or kitchensink before you start to work.