I've only found that the spring needs replacing if it snaps from fatigue. As mentioned it could be that the bolt on the brakes is too tight. Could also be there's too much friction in the cable housing. I'd try releasing the cable to isolate the problem.
Here is one of three offset-brake wrenches. Just ahead of the anchor-bolt after it goes through the frame and is approaching the actual body of the brake - you should find a part of the bolt that has a flat-area in the vertical. These fit this and you can rotate the entire brake into proper alignment. Using a cone-wrench works perfectly as well - if you have the clearance to deploy one.
From you post I'd say it's over-tight fixing bolt. Is that the bolt that holds the cable, or one of the bolts that holds the caliper into the frame?
The bolt you're worried about is the one that fixes the calipers to the frame. Back it off a bit, then follow the directions on the ParkTools page referenced above for adjusting tightness and centering. The problem's not with the cable, it's a small fix on the brake itself.
Springs rarely go bad on caliper brakes. I mainly fix up old bikes from 70s and 80s with crappy old centerpull and low-end sidepull caliper brakes, and I've never had a bad spring.
Also how often should one replace brake cables? I've got it close to working properly and noticed the brake cable seems a little slack. The cables are about 2 yrs old and seen a few thousand km's...
pads have already been changed once.
When I find rusted cables, I swap them out, to minimize the grit that gets into the cable housings. As long as they don't have frayed/broken individual wires, they're usually fine. The main thing one has to maintain is the length and tension. Not a lot of need to check anywhere other than the ends, as the parts that run inside the housings are usually protected from wear, age and the elements. The greatest stress put on a cable is at the end attached to the lever and at the end bolted into the brake caliper--that's where to check it over.
If your cable is slack, I'd say look at the ends and the tension; if it's looking old and worn out, might as well replace it--new teflon-coated or stainless cable sets run about $$7-$12 at an LBS, and your bike will love you more for it. If you can't afford that, just make sure you attach it with proper tension to the calipers.