1.) Open your image in Paint
2.) Assuming that this is an object (see below for help), go to Mask -> Create -> From Object
3.) The mask marquee will now appear around your object. Go to Mask -> Mask Outline -> Border
4.) Pick the pixel width you want for the border. The mask will no be a border of that many pixels wide, in a border around your image.
5.) Fill with the border color of your choice (right click the color, fill with the "Paint Bucket" tool.
If the image is not an object to begin with, click on Object -> Create -> From Background - this will make the background an editable object.
This assumes v11 or higher. It is similar for older versions, just a little different menu choices.