I've soldered to a lot of stars, with lead-free solder, and I've rarely had any difficulties even when they're fixed to decent heatsinks. No added flux, no pre-heating.
I use a temperature-controlled iron, with a reasonable-sized bit (2.3mm wide oval). Usually I tin the pad first, then solder the wire later in a quick action.
I normally use PTFE-coated wire, since though it's a bit harder to strip, it gives a neat result with fine wires with no insulation melt-back, and the wire I use has silver-coated copper inside which solders really nicely and very quickly.
That said, having used Luxeon/Seoul/Crees for the last 12 years, I recently had to solder to some LEDEngin stars for a UV project, and they were all a real pain - it was far harder to solder to those stars resting on a soldering mat than to other stars well-fixed to big heatsinks.