JPEG format is not like text document, where you can correct one letter and size of the document won't change.
In JPEG when you edit even two pixels, whole image will be rebuild and repacked. Your images might have compression factor of 65, but MS Paint has fixed factor somewhere between 75 and 85 (do not quote me on that though).
MS Paint has average default settings for saving JPEG, which are might be good for some pictures, but not for others. For MS Paint settings are fixed, pre-programmed, and you can not change them.
Thus, I would recommend using othe software where you can manually change saving quality factor,
like
paint.NET