Your understanding of the factual situation is essentially correct.
Here is an excerpt from a (multi-)book review by Timothy Snyder, a leading historian of the era:
After the German annexation of Austria (or Anschluss) in March 1938,
some twenty thousand Jews with Polish citizenship living in Austria
tried to return to Poland. After humiliating pogroms, Austrian Jews
were subjected to a systematic policy of expropriation and forced
emigration devised by Adolf Eichmann. As these methods were then
applied to German Jews, Polish diplomats feared that the tens of
thousands of Polish Jews living in Germany would also seek to return.
The foreign ministry decided to exclude Polish Jews abroad from the
protection of the Polish state.
Right after the Anschluss, the Polish government demanded that all of
its citizens living abroad register with embassies—and in October,
right before the deadline, instructed its ambassador in Berlin not to
stamp the passports of Jews. The Germans could see where this was
headed, and responded by deporting about 17,000 Polish Jews to Poland
in late October. Very often these were people whose entire lives had
been spent in Germany and whose connection to Poland was quite
limited. Grynszpan’s parents, for example, had moved to Germany in
1911, before an independent Poland had been established. Their
children had been born in Germany.
Grynszpan’s parents had sent their son, then fifteen years old, to an
aunt and uncle in Paris in 1936 to spare him from Nazi repression. By
1938, both his Polish passport and his German visa had expired, and he
had been denied legal residency in France. He faced what his
biographer Jonathan Kirsch perceptively calls the “existential threat
of statelessness.” His aunt and uncle had to hide him in a garret so
that he would not be expelled. They shared with him a postcard from
his sister, mailed right after the family was deported from Germany to
Poland: “Everything was finished for us.”
However, I submit that the lens of "illegal immigration" is a completely anachronistic one for the pre-WWII era.
I presume you are trying to draw some contemporary insights but there are probably none to be had except that the Nazis were monsters and far too many people and countries were indifferent bystanders who did nothing to stop them. Standard fare.
As far as I know, most countries - with the insalutary exception of the US -did not place limits on immigration back then; it was just not that much of an issue.
Moreover, the question is not really - and has never been - whether the German policy towards the Jews (and others) was legal (I guess in a narrow sense it was - there was no UDHR back then, for example). Rather, whether it was cruel and inhumane.
For example, were the Nuremberg Laws illegal as such? Probably not, as they were duly voted in by the Reichstag etc. But they sure were evil, cruel, and inhumane. And they should have been stopped in time by those who could have done so.