Neither the "mini-shuttle" nor the retired shuttles are in a position to reach the orbit of the NK satellite. It is in a sun-synchronous orbit, which means its orbital inclination is near-polar. The current OTV-3 (mission name of the so-called mini-shuttle) is in an orbit of around 40 degrees, which makes it incapable of reaching the NK satellite's inclination, and no space shuttle ever flew in a polar orbit and nor had any plans/capability to do so after the Challenger accident.

If I had a nickel for every time I've seen someone propose that two satellites get together in orbit when such a thing is practically impossible, I'd be hundreds of dollars richer...

Believe it or not, this long route (via the Earth-Sun L-1 (Lagrange-1) point is a lower energy trajectory (that is, it takes less energy to send the probes) than the more direct route followed by the Apollo missions. This allows for a smaller launcher (or conversely, a larger payload for the same sized launcher). See http://www.nasa.gov/pdf/582116main_GRAIL_launch_press_kit.pdf.

A Progress was the payload. The rocket is called Soyuz. (As are the payloads that carry humans.)