The GNU Image Manipulation Program (GIMP)
How to
Restore pictures
captioned newspaper photo
scan at 1200dpi+10bpp
gaussian blur (50-100% of dot distance)
if the image is in colour, it can help to separate the scan into CMYK or RGB layers and blur them independently
use clone tool with a soft round brush
scale down.