[mlangsdorf]

This is a fantasy game set in a fantasy world, not a fantasy game set in medieval England. The situation is similar to the succession of Henry IV from Richard II, and the PCs have reasons to prefer that the Edmund de Mortimer analogue be on the throne rather than the Henry IV analogue that is currently on the throne. However, the game is not set on Earth and appealing to the Pope in Rome or the King of France is not an option.

Recapping possible solutions, and throwing out another request for ideas for other ways that people might handle this if they were PCs:
* Cut a deal: Get an audience with the current king, and cut a deal with him so he does what you want. It's probably not as good a deal as you could get from the other guy, but it won't backfire spectacularly.
* Persuasive Abdication: Get an audience with the current king, and convince him to resign. I'm not even sure how the PCs would do this.
* Delegitimize the current king: get religious authorities to sanction him, demonstrate he has lost the mandate of heaven, convince the aristocrats the law the king used to remove the previous heir presumptive from the succession was invalid. All of these are difficult approaches, and have the problem that the current King may still have enough support from the military and tax collectors to ignore being delegitimatized. Even if mostly successful, this may lead to a civil war.
* Coup de main: Arrest the current king and his supporters, put the preferred person in place. May lead to a civil war, either because the arrests failed and enough supporters escape to rally loyal forces elsewhere, or because the coup is not seen as legitimate and there's a general rebellion.
* Assassination: Kill the current king and his immediate descendants. Might cause trouble with the new king; might fail and cause a civil war.
* Outside invasion: Since one of the PCs' goals is to borrow the kingdom's army to fight a different enemy of theirs, killing a portion of the army to subdue the rest is not as good as acquiring them peacefully.
* Civil war: This is probably not a plan, because it's the same as an outside invasion only without using the PCs' known, reliable troops. However, it is an outcome of other plans that go wrong.

I think I can prepare for any of these, but I'd like to have at least some notes ready for any approach the PCs take.