Thank you for your reply.
I tried really hard (several hours) now to reproduce the issue on a clean WordPress install (and not just all other plug-ins than Custom Permalinks and Polylang deactivated).
I am unable to reproduce that exact issue now (the one with the PHP Warning).
The only issues I get now are redirect loops.
So I am guessing it’s a more complicated problem that has to do with the way and order things were updated and installed over time.
The problem with Polylang is, that it changes the way permalinks work (i.e. Prefixes other language pages with /two-letter-language-code-here/ and I guess that does not work well with Custom Permalinks, because it changes that too.
Thus Polylang and Custom Permalinks are unable to work together at the moment I guess.
Thank you for your time.