Whenever anyone plays a lawful character it is a good idea to hash out ahead of time exactly what code or body of laws the character is beholden to, what is the characters heirachy of allegiances, and so forth. Alot of problems could have been solved had the DM made things explicit to begin with.
I hate to criticize a DM based on the word of a player, but it sounds to me like your DM is in the wrong.
Even if Cyre is gone and its people scattered to the winds, your Paladin is still loyal to the nation of Cyre in what ever form it is in until explicitly and formally transfering allegiance to something else or until some authority which the Paladin recognizes as legitimate orders the Paladin to transfer allegiance and is in doing so not seen by the Paladin as guilty of bretrayal himself. I don't know much about the setting, but if the Cyrean Avengers represent something which is in any way like the legitimate government of Cyre in exile or are in any fashion loyal to the idea of the nation as much as the Paladin is and aren't merely a band of honorless bandits, I would very much think it against your code of alignment to not treat them as peers or even lords.
The big sticking point here would be what was your explicit 'word' to the King of Breland. Did you in fact promise explicitly to do something for him? Did you give your word? Because if you foolishly gave your word to do something your higher allegiance requires you not to do, you are screwed. The only thing you can do is break your word to the King of Breland, seek atonement to your diety, and go to the King of Breland and confess. But if you didn't give your explicit word to turn over the man to the King of Breland, if you kept your silence and allowed the King of Breland to decieve himself, or if you only promised to 'bring him to justice' then you have the out of obeying the letter of your word.
Sometimes there really are situations where a lawful person can put himself in which its impossible to satisfy his obligations. A DM is under no obligation to keep you out of these traps or tell you how to get out them. A wise lawful person avoids putting himself in those situations, and is always thinking ahead to the implications of any action he does. A wise Paladin is also going to be able to find legitimate exceptions in his code for particular cases, or is going to be able to word things in ways that he can avoid legal traps. In fact, the ability to get out of seemingly insolvable legal traps is often seen as a sign that the Paladin truly is on a mission from god.
I'll give a historical example. At the sham trial of Joan of Arc, the prosecution was continually looking for some excuse to condemn her as a heretic (note that this was a legal fiction itself because under the law of the day heresy was only a capital offence on the second offense). One of the legal traps that the prosecution tried was asking Joan the question, "Are you in in God's grace?" If she answered, "Yes.", then she would have been guilty of a heresy because Catholic doctrine taught that no one could know if they were in God's grace. If she answered, "No.", then it would be as much as admitting that she could not have been on a mission from God and therefore her guilt. It was therefore an insolvable problem. Joan answered, "If I am not, then may God put me there. And if I am, then may God preserve me in it." Hearing, this some members of the prosecution said later that from then on they feared damnation, for they knew that they were dealing with "a holy woman".
Playing a Paladin well is hard. I confess I've never even attempted it.