Just to follow up... I was playing with the DK graphic roms... and as I suspected... color palettes are the issue.
So, yes, I can easily switch the graphics on the roms so that Pauline saves Mario... but changing the palettes is a bigger challenge. Pauline will wear a blue dress and have red hair (fine with Jop I'm sure), and Mario will have yellow overalls and a pink shirt. It looks like crap, and not worth sharing.
Fixing the color palettes for both characters would require someone who knows more about the dk code than I do.