As Oskar already said, you'll always have some quality loss, but the Paint program that comes with Windows is terrible for color conversions like this, pretty much any tool will produce better results. You could use a powerful image editor like GIMP or Photoshop, or a more advanced Paint-like program like Paint.NET, but a tool like Irfanview is also a good choice if you just need to convert some existing images.
Here's a comparison I did a while ago (this was for textures, which require the same conversion). As you can see, with Irfanview you'll hardly see any quality loss even with images that contain a lot of different colors and gradients. For 'easier' images like the cobblestone texture, any half-decent tool is good enough already: