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 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.