Take him back to the Cyrean king, and let Breland know what is going to happen. Talk with the Cyrean king about the debate -- that another nation also wants a say with this man, and that rash action (such as execution) would be unwise. Acknowledge the debate, but know which side you lie on.
I don't think you're in danger of losing your paladin status or violating alignment for it at all, regardless of what you do. Either situation is "acceptable," there's not a right and wrong answer, there's two right answers: both of them.

It's your call which authority is binding on you at which times.
As long as you want to respect Breland's laws, and show respect for them, even in violating them, there's no real conflict. But you're not a citizen of that nation, you're not an agent of that nation, and you have no allegiance to that nation. Let them know as such: "We are taking this man to punish him for crimes he comitted against the people of Cyre, to do justice to him. If you wish to argue this point, you must argue it with the King of Cyre, not me. I am an extention of my king's will."
Even if you have to use secrecy to get him out, let them know once you're safe, and argue their case before the King of Cyre: "We were guests in their lands, and we were rude guests. I am not in your shoes, Majesty, but I would recommend diplomacy to save our honor. I would be happy to volunteer for such service, as I was your agent who wronged our hosts."
There's no one right answer to this, there doesn't have to be. You could be fighting agents of Breland who were also paladins, and neither of you would loose status for killing each other.