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.
Plumbing solder is generally kind of thick - more than 1/8 inch. Electronic solder is usually much thinner - less than 1/16 inch.
You can tell if solder has a core by melting some on a piece of paper - it will leave a greasy, maybe sticky spot if it has a core.
Thin solder that leaves a sticky spot when melted should be electronic solder.
As @EJP says, the problem is usually a break in the cable near the plug. Cut the old plug off maybe an inch from the plug, strip the wires on both sides of the cut. Use an ohmmeter to find out which wire goes to which part of the plug, and solder the wires on the other part of the cable (the part that goes to the headphone) the the correct places on the new plug.
Best Answer
There are two problems:
Heat
A motor is a large piece of metal, so the heat applied to one spot will quickly spread to the large volume. As you don't want to heat the complete motor to soldering temperature, you have to apply the heat as fast as possible. Choose a high power solder iron or at least set your iron to the highest possible temperature. I also prefer a small torch. (But be careful, it can easily overheat your motor and damage it)
As said in the comments, it also takes long to cool down, so make sure that the motor and the wire don't move while the tins is not yet solid. Holding by hand is not a good idea.
Material
Solder/flux used for electronics works well for metals found in electronics, e.g. copper, tin, gold, but also zinc.
On the other side, iron can not be soldered that easy. The tin will roll off just like water from a waxed surface. To solder iron, solder tins with a high fraction of lead are used, as well as flux based on zinc-chloride. In my experience, electronics solder tin and zinc-chloride based flux usually work fine for a reasonable conductive connection. The special solder tins for iron also require a higher solder temperature. Note that zinc-chloride is quite aggressive and you should carefully remove it after soldering.
However, many iron parts have a zinc coating and can be soldered without problem. But parts are often also coated with some painting, e.g. a thin yellow-greenish painting to prevent corrosion, and of course, you have remove it before painting. May be, you manage to remove the painting but keep a zinc coating.
There are also other metals like aluminum which are quite impossible to solder.