The regulations which Data quotes don't make sense.
Any government has the right to control immigration, including finding illegal aliens and expelling them even after they have lived there for years.
Any government has the right to deport legal immigrants if they are convicted of revolutionary or criminal activity.
Any government has the right to make laws and punishments. All governments have the right to banish and exile their citizens, as well as deporting illegal immigrants and legal immigrants who have violated various rules.
If Mistress Beata sentenced the Odin's crew and their wives to death but commuted it to deportation and permanent exile if the Enterprise took them away today, Picard would have only two choices according to the rules of diplomacy and the Prime Directive. 1) let them be executed 2) agree to facilitate the exile by taking them away. Picard had no legal justification for trying to persuade Mistress beata to chose any third option.
The idea that Starfleet is legally unable to assist a foreign government to exile and deport undesirable Federation citizens is absurd.
If the federation had such a law foreign governments would suspect that any undesirable Federation citizens which showed up on their planet were not actually acting on their own but were secret agents of the federation on a mission to change their society in direct violation of the Prime Directive.
Perhaps that is the real reason why the Enterprise carries so many civilians. Some of them may actually work for Section 31 or something and may be ready to infiltrate any society the federation disapproves of, with the captain claiming he has no authority to remove Federation citizens against their will!