I spent quite a while tonight on the top image trying to remove the two poles. No matter what I tried I still have some tell tale marks in the sky. I was wondering whether any of you have some different techniques for removing unwanted objects. In this image I tried then patch tool and healing brush but neither work well near edges. In the end I carefully selected parts of either pole, move the selection to a nearby part of he sky which I copied and pasted over that part of the pole. It worked well most of the time except a couple of areas around the lights where the sky was a little lighter.

Have tried to clean up the ghost marks with the cloning tool at 50% but cant manage to completely get rid of them. Am thinking maybe I may have to start again from scratch.

A higher res version is at this link for anyone keen to have a try.
http://www.flickr.com/photos/71804519@N00/2467189951/

I used the healing brush to clean up what the patch tool didn't get... getting a new sample point when necessary. The 2nd image shows before the healing brush was used. I also went into the bushes between the vertical fence pieces with the clone/stamp tool. Then painted a little on the top of the windshield to remove some orange highlighting caused by lights that aren't there anymore.

You're pretty much screwed into cloning the foreground.

As for the sky? I'd drop in an entire fake sky from the bridge to the left.

Color a new layer the pinkish color at the horizon. Set your gradient tool at 35%. Take a color reading at the top and "draw" gradients in slightly different directions from the top down.

Add some noise into the colors you use and then blur it slightly. It'll look grainy and blend right in. Layer mask out the bridge and foreground.

Sometimes it's easier and better to just replace what's wrong.

Thats a great job. Just to clarify - did you start from scratch using the patch tool. I found I had to do it in small chunks as you run out of destination space to drag the selection to. What settings / brush size did you use on the healing tool. I just had another try with a bigger (healing) brush with better results.

For the patch tool I selected each light pole individually one at a time from above the very top of the pole down into the tree. I did the right pole first and after doing that I had more clean sky to use for doing the left one. Source is selected in the options so dragging with the patch tool shows a preview of what's going to go into the selected area. They weren't really tight selections... just loosely drawn keeping some sky inside the selected area to try and avoid the weird edges - the only place I got one I didn't completely expect was the upper left corner from the left light.

I do use a Wacom tablet and that helps but there's very little that can't be done with a mouse. For my healing brush my hardness is at 50%. I'm always resizing it using the [ and ] keys trying to keep it sized to what I'm trying to get rid of but I'd bet it was about 25 to 30 pixels for the upper left area of sky. I didn't resize the attached images - they are the size I worked at. I just right-clicked and saved the image from this (http://www.flickr.com/photos/71804519@N00/2467189951/sizes/l/) flickr page. I think it usually works best it it's sized a little bigger than the area I want to clean up. There's a little bit of science to this stuff but I think it's mainly technique and that will get better the more you play around with things I think. The main problem area in the image you posted wasn't really large so I don't think you were way off on what you were doing.