If you're looking for good automated algorithm, then for hand-drawn sprites there are few:
2xsal
hq4x
4xbrz
You should be able to find stand-alone scaler for most these algorithms. For every image, we could try them all and select the best result.
http://en.wikipedia.org/wiki/Image_scaling
Of course, this is nothing compared to what artist could do with extending a sprite by hand.
Note that in KeeperFX GFX sources there's "textures-160" subfolder - it contains textures rescaled by Synesthesia (and some which he never touched which are rescaled by simpler ways).