The areas behind the watermark are mainly blocks of solid colour. Any graphics package (even MS Paint) will let you zoom in, pick a colour from the picture (with the eye dropper) and then use that colour with a pen (or brush) to go over the watermark. It would be fiddly but i bet you could do it in an hour.
There is also Gimp (http://www.gimp.org); it has many of the same functions available in Photoshop, including the one everaja mentioned (I believe Gimp refers to it as Clone Tool) - and best of all, it's free.
But I also agree with newflesh: just ask for permission to use the image Aleator. Depending on your use case you might have to give credit to the author somehow, but most people on Deviantart will be happy that their work is getting attention, and are probably willing to help out and / or reach some sort of compromise.
Don't know how to use it 