I wouldn't use the clone tool for this job... layers is much easier. I used PS for this fix, took about 90 seconds. I believe that Paint Shop Pro 2x has layers so you should be able to do this as well.
The approach I took was based on the fact that you had a beautiful blue sky with a smooth gradient. I just duplicated the underlying layer, created a selection that surrounded the affected area, and then covered it with a blue gradient that matched the dark blue to light blue transition of the sky on the top layer. I then added a layer mask, inverted it, then painted (on the mask with white) to add the sky back in and cover where the tree was in the way. I zoomed into 400% to do the tight edge edits, but most of it was pretty straightforward.
Took longer to type this than to do the fix.