Background: I've got a lot of old photos taken by my first digital camera Epson PhotoPC 600 from 1997 and I'd love to make them look as good as possible. I do know they'll never look like those from quality modern cameras, but I want to get the best possible results.

Problems: The pictures are in an 1024x768 resolution (I'd like to get 2048x1536 for viewing on today's screens) and cannot be easily upscaled due to weird, staircase-like (poorly interpolated) edges.
The other problems are: Specific (non high-ISO) noise, low dynamic range, lower contrast and saturation, chromatic aberration and others.

Question: What are the recommended operations/steps (and their order) to fix the images in the best possible way?

Note: I'm attaching a few sample cutouts showing the problems mentioned.

Edit: If you process some of the samples included, please specify what have you done on them (what filters, what software etc.)