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.
Sn96.5/Ag3.0/Cu0.5 solder's liquidus is 217 °C, and good old 63/37's eutectic point is 189° C. So yes, you have the temperature turned up much too hot. Most parts are rated for 260 °C for 10 seconds max. Soldering at the temperatures you have been using can potentially damage components, has been weakening the glue under every pad you solder (the copper is glued to the FR4), producing significantly more hazardous fumes, something that is already more hazardous with lead-free solders, and generally does nothing good.
I think I know why you have your iron turned up that high. If it is, and no offense intended, a crappy iron or even a good iron with a crappy tip, you will need to turn it up to a much higher temperature than normal to overcome the crappy tip's crappy thermal resistance to start a joint. However, once the joint is solidly wetting the tip, the thermal resistance drops significantly, and the joint will experience those too-high temperatures in full force. So even if it seems like that is the temperature that is needed to begin melting solder in a reasonable amount of time, once it is melting, it may get much too hot.
In fact, I had a Hakko iron with a crappy fake tip and I constantly had it set on the exact temperature range you are using for lead-free soldering, at least until I realized what was going on. Sometimes I even bumped it up to 400° C. Which I now know was a bad idea.
There is a very simple way to tell if your iron's tip is a good one or one you shouldn't be using for real electronics work. Remove it from the iron and use a magnet to see how magnetic it is. It should not be magnetic at all, or maybe very very weakly magnetic. Good tips have copper cores, and maybe a thin steel jacket or shim inside, but otherwise no significant amount of ferromagnetic material. Bad tips will use steel/iron, as it is much less expensive. Unfortunately, it also will result in a tip with on the order of 6 times the thermal resistance, which is really not OK.
OK, now I can finally answer your question!
Those dark splotches are leftovers from the resin-based flux. No-clean fluxes are often made out of water-soluble resins (vs rosin) and during heating, most of it will evaporate away. Usually, there are some inert solids left over however, and high temperatures will cause them to oxidize (or something) and turn brown to black. These solids are very much the opposite of what the solder wants to wet, so it will be clumped and pushed to the surface of the molten solder joint. It should come off but probably only with some rough scraping, like with a wire brush. As far as I know, it should not have a meaningful impact on the joint, but if you want to avoid this, I suggest lowering your iron temperature (and possibly getting a new tip and/or iron depending, so soldering is effective at said lower temperature), though this may not totally resolve the issue. Sometimes, there are just some inert impurities in a particular batch of solder flux. It's ok as long as it is pushed out of the joint to the surface, which it almost always is.
Oh, one last thing: no clean flux isn't. It ought to be called "no urgent cleaning", but most fluxes labled no clean will certainly leave a film or residue behind, and while they are not going to completely eat away the copper of a trace if left on the board for a few days or more, I have heard that they aren't always as inert as people seem to think. It could still cause problems, albeit on a much longer (months) time scale. But, most of what is in this paragraph is simply things I've heard from other engineers I trust, but I don't have any actual data to back it up, so bring a bag of salt etc.
Best Answer
Technically, the unevaporated flux will form voids in the solder and mechanically weaken it. Additionally, the non-conductive voids will slightly increase the overall resistance of the connection.
But.
You should be aware of an old saying:
Your approach should incline toward the military philosophy. If slight decreases in mechanical strength are an issue, you are guaranteed to be be counting too much on your solder. Physical strength of a connection should always come from physical aspects. For instance, don't connect two wires by laying the bare ends side by side and soldering: twist them together first. If you're soldering a PC mount transformer to a board, you MUST provide mounting screws. Things like resistors and (non-electrolytic) capacitors are simply not going to stress the joints in normal operation. If they do, you're working in a high-vibration environment, and even counting on perfect joints will not save you.
In a similar vein, solder provides something like a perfect (sub-milliohm) electrical connection, and a slight increase in resistance should not cause any real problems. If you're working at current levels where self-heating might be an issue, you already have to worry about self-heating of the conductors themselves, and you should be looking at purely mechanical (such as crimping) connections. If you're worried about extra voltage drops or changes in effective resistance, you're working at such low impedance levels that you need to be paying all sorts of attention to the circuit details anyways, and letting the flux completely react will be part of your process already.