I put the soldering iron all the way up to 420C.
The hotter, the better. The idea is to melt the solder as fast as possible, before the heat can dissipate through the board and damage other things.
I have had problems when I have kept the soldering iron tip on the board for too long. This can happen if your tip is not hot enough, if the solder melt temp is too high, of if the board is too thick and the heat dissipates sideways before the entire column of solder can melt.
I suggest that first you apply a little liquid flux compound to the old solder, this will make the solder flow better.
Then you should melt a little new solder on to the old solder. That will increase the surface contact area between the iron and the old solder and increase the rate of heat transfer.
As orgwood has stated in his post, you melt one terminal and rock the capacitor a little and then melt the other terminal and rock the other way. Back and forth until it is free.
The last part is to get all to old solder out of the hole so you can slide in the new cap. That is where the solder sucker is used.
Electrolytic caps are polarized, the side stripe indicates the negative terminal. So be sure the stripe is on the correct side when you insert the new cap.