Paint does not natively support 256-color palettes (all it has is a few swatches, it can't hold all of the colors). For that you'll need another program. What AJ said will indeed work. If you go into XWE or another lump-editing utility and extract a sprite lump, the 256-color palette will come with it, and as long as you have a graphics program capable of handling 256-color palettes, the palette will be loaded with the picture.