I can give you the instructions for Photoshop that maybe someone can translate to Gimp or Paint.NET

This method is done with selections, masks and adjustment layers with no manual brush editing required. These simple examples take less than a couple of minutes to fix.
Let me know. :)
Edit:
OK, so I've copped some flak for not posting a Photoshop solution, even though the OP said he couldn't use Photoshop. Here it is anyway.
Settings provided are for the 2nd image using PS CS4...
- Select menu -> Color Range...
- Select: Samples Colors
- Localized color clusters: Off
- Fuzziness: 163
- Create a new Hue/Saturation adjustment layer. This will take the selection and apply it as a mask on the adjustment layer.
- Desaturate the color area (Saturation: -100)
- Lighten the dark area where the color was (Lightness: +74)
- Add another Hue/Saturation adjustment layer and desaturate the entire image (Saturation: -100)
- Optionally flatten all layers.
Depending on the severity of the marks, you could optionally use the brush tool to modify the mask after step 2. You can also use the Dodge and Burn tools after step 4.