It's a female pin header, most likely 0.1"/100mil/2.54mm (but use your calipers to verify). The little metal pins are for soldering into a PCB, whereas the corresponding male connector plugs into the contacts embedded within the plastic housing.
Also note that they are available in "stackable" form, where the metal pins are long enough for the connector to act as both male and female; these are used on both PC/104 expansion boards and Arduino shields so that they can be stacked multiple devices high.
You bought a reasonable solder. Sn63Pb37 is a (close to) eutectic alloy, so it has a bit more of the more expensive element (tin) and is a bit better than Sn60Pb40 solder. As a result, it melts at a bit lower temperature and (more importantly) it's a bit easier to use because it solidifies suddenly rather than going through a mushy phase where it's easy to create a "cold" solder joint if the parts move during cooling.
0.025" (0.635mm) is a reasonable size for general purpose. I use 0.8mm and 0.38mm.
Personally, I prefer Kester 44 because the "no clean" flux leaves a nasty residue that is very difficult to clean off. For most applications it's just fine, but for sensitive high-impedance analog circuitry it can be a problem. I had an application with 5-50K resistors where it was a problem, because of extreme accuracy requirements. The contract assembler had used no-clean, contrary to instructions. The Rosin RMA flux may look ugly if you don't clean it, but it seems pretty inert, and it's easy to clean with solvents. I doubt you'll see any problems with the one you chose.
You say "solder station". It's temperature controlled? That helps.
You don't need to buy any extra flux for through-hole parts. You might want to buy a flux pen (eg. Kester #186) if you intend soldering surface mount parts- it helps a bit. They look like a felt-tip marker but dispense flux. Unfortunately, they seem to be a bit hard to come buy these days. Bulk flux attracts Hazmat shipping charges.
Make sure you're dealing with "fresh" parts. If they've been laying around in some surplus shop oxidizing for a decade or two, they're not going to be all that easy to solder!
If the tip is well wetted, you should be able to touch it to the two parts at once, feed the solder into that pool, and stop when you have a fully wetted joint. It should be shiny and smooth when it's done. Practice makes perfect.
I suspect if you've had problems with soldering, other than technique, your parts are the source of the difficulty rather than the solder or soldering iron.
Best Answer
40W is MUCH too much heat for small pins. The reason it barely melts the solder is because you haven't kept it clean and tinned, and the tip has probably burned. I suggest getting a new iron and TIN the tip IMMEDIATELY, while it's heating up for the first time. A 15-watt iron will be sufficient for soldering pin headers like you showed in your question. A tinned tip will allow the heat to be transferred to the pad and to the pin, allowing solder to flow properly.
Right now you're using way too much heat, and it's melting the plastic around the pins. Soldering of a single pin should only take a couple of seconds maximum with a proper clean, tinned tip. That is not enough time for the plastic to melt.