I've been using Microsoft ICE for close to 10 years now. I've also tried Hugin and Lightroom and Photoshop. I always end up using ICE. Doesn't hurt that its free. It has a fair degree of flexibility in choosing a perspective model and in 2D stitching, etc. Hugin does too, but it is MUCH more complicated to figure out and use. Lightroom is OK, and it's nice to be able to stitch raw files and preserve all the data, but the resultant files are huge and I don't find it has much flexibility.
The background fill option in ICE works very well, as does content aware fill in Lightroom and Photoshop. Occasionally I'll prefer Lightroom's fill to ICE and use that program, but the vast majority of the time I use ICE.
I strongly recommend that (assuming you are on Windows) you download and try ICE. I think you might be pleasantly surprised at how well it works for a free program.
Peter