Note: All important settings are highlighted with a red ellipse.
This information relates to Paint shipped in every Windows version.
Note: Microsoft Paint automatically produces uncompressed files.
First reduce the image to palette format:
In the Save as... dialog, use Uncompressed: