I had a few issues when using it though:
As you said it gets a bit long to process everything when there are many colors. I noticed many results are not relevant, just as images lacking contrast making the sprites not “readable”.
Maybe there could be an option to only try a palette color on an initial color with a similar level of brightness? This would preserve brightness contrast (although not hue contrast).
Then we could have another option to make sure that the same color is never used twice, assuming the palette has at least as many colors as the original image.
We could also have a special case where palette colors = initial image colors: in this mode, you only need to input one image. Then it effectively does a color permutation, in the sense that it remaps every color to some color in the initial image, bijectively (two different colors map to two different colors; and since the initial and target number of colors is the same, we also cover all colors in the final image).