I am not an expert on this, so take with a grain of salt.
But why not research how you might make graphics if you were working with the tools of the era? If you were using Deluxe Paint for the Amiga? While making a slick vector and then downsampling on export might work, it might be better to pick your 256 colors and build your image pixel by pixel.
Or, perhaps you could find some screenshots of the NES games you want to emulate. You can then sample the palette to see what kind of colors you can work with, and you can take a close look at the sprites that they have to see how the graphics were made. Megaman in particular had very expressive character sprites, even though they were just a few pixels tall compared to today! The look and feel of Mario is the first thing that lots of people would think of when you think "8-bit," so if you want to evoke the feel, print some screenshots and keep them on your desk as you create.