I'm a bit skeptical of your claim that "getting a work permit in Europe basically isn't possible without a degree". Is it an EU country? In every European country I've had direct experience with (DK, DE, IT, PT, FR, BE), you can get a residence permit with the right to work by applying as an accompanying spouse, or under a family reunification scheme. Of course, in some countries this can take time, but certainly not…
I would also add that every EU country I've looked at also has an "or equivalent work experience" clause for their tech/skilled-path work permits that would void the education requirement.
I work for a university that's a short drive from the US border, and yet had to harangue HR into applying for a NAFTA/USMCA work permit (which is easier) instead doing the "standard" thing.
It's worth spending some time figuring out what you are eligible for so you can at least try to put them on the happy path.