@Intrepid:
I’m pretty sure you’d want to use almost anything but Paint. I only use Photoshop, but that’s a steep investment and without serious experience as a digital artist probably overkill.
GIMP is free, and generally well-regarded. I know I’ve also used Pixlr in a pinch, but not sure how large of files it can handle.
Google is your friend, I’d search “best free Photoshop alternatives”
Photoshop and GIMP are great for editing existing images like photos and other artwork, but if you want to create something like a new map from scratch, I would recommend using a vector-based program instead. Unlike Photoshop which is primarily geared towards modifying and compositing existing images, these programs are designed specifically for creating complex images from scratch. Also vector graphics are scalable, so you can adjust or resize whole images or individual image elements without any apparent loss of quality.
Adobe Illustrator is the obvious choice here if you have access to/can afford Adobe products, but if you’re looking for a free option then I would highly recommend Inkscape. It’s a very lightweight but powerful vector graphics program that you can download it and use for completely free at https://inkscape.org/en/.