The wording of the spell matters
If the characters are aware that there might be an impostor and they word the spell carefully, then the spell will fail. For example "Show me Sir Galahad the Great, rightful King of Brittax, Friend of Elves." The polymorphed minion is not this specific person and the spell will fail.
However if they simply state, "Show me the king of Brittax," you have more leeway in adjudicating the results. In this case the rightful king is dead and the polymorphed minion is the king of Brittax and so the spell will very likely indicate the polymorphed minion. Of course the Locate Creature spell does indicate (PHB 256):
If the creature you described or named is in a different form, such as being under the effects of a polymorph spell, this spell doesn’t locate the creature.
Is this relevant in this case? I would say no, because the creature is the king because of the polymorph spell. They are not in a different form (than what was asked for) because of the polymorph spell, they are in the desired form because of the polymorph spell. They are only the king because of the polymorph spell.
Lastly, if they say something like, "Show me the rightful king of Brittax," they may be guided towards a third NPC who would be the heir to the throne if it was known that the rightful king was dead.
Is the target familiar and known to the caster?
It's important to consider the limitations the spell places on who you can specifically locate. The spell description states:
Describe or name a creature that is familiar to you.
and
The spell can locate a specific creature known to you, or the nearest creature of a specific kind (such as a human or a unicorn), so long as you have seen such a creature up close — within 30 feet — at least once.
This text is not overly clear, but it does suggest that if you've seen a specific creature within 30 feet they are known to you and the spell will work (barring other limitations). Familiar to you can mean a lot of things: It could mean you know of the person, or it could mean you are personally acquainted with them, or as the text suggests it could mean you have seen them once. As a GM, be sure to consider and interpret these statements when you resolve the effects of the spell. In the context of the party you describe it is very likely the PC has seen the potential targets of the spell. Also they may have met at other times in the campaign, or may just be known to the PC.
If I were the GM I would casually ask the spellcaster who they are targeting with the spell and apply the wording they use in-game to rule how the spell functions. As long as they are familiar with the target then the spell can locate that character.
In short
Yes the spell could fail, and you can play with the results depending on how the spellcaster PC words the spell and their familiarity with the target
In regards to Nystal's Magic Aura, this spell would not affect Locate Creature in this case because the PC is attempting to locate a specific person, not a type of creature. NMA description states (PH 263):
You choose a creature type and other spells and magical effects treat the target as if it were a creature of that type or of that alignment.
When Locate Creature is used to locate a single creature it is out of the scope of Nystal's Magic Aura because you are not looking for a type of creature.