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:
