Thank you so much for pointing me in the right direction. The step I was missing was to remove the keyring entries on my desktop app.
I decided to completely reset everything and to start new. There seem to be several issues - with only the last one killing the experience:
Creating an encrypted folder with Desktop app first
When creating an encrypted folder with the desktop app first the Android app does not allow to enter a pre-existing mnemonic and always generates its own mnemonic. Tried removing/re-adding the account from the app and also completely uninstalling the app. It just never prompts for the desktop mnemonic but generates it’s own.
Creating an encrypted folder with Android app first
The other way around seems to work (with one inconvenience): when creating the encrypted folder with the Android app and then setting up the desktop app the desktop app works as expected. It immediately prompts for the mnemonic. The inconvenience was again the Android app: when setting encryption on a folder it shows the mnemonic. I copied & pasted the mnemonic into a password safe and tried entering the mnemonic in the desktop app and failed with an error. After a while I discovered that the Android app did not use the displayed mnemonic but created a new one. Luckily it is possible to show the mnemonic from within the app again and I was able to copy & paste the correct one.
Remaining issue
The main issue now: all files uploaded through Android app work fine on the Desktop app.
Sadly when uploading folders & files through Desktop app the Android app does show the Folder but does not list its contents inside. Error message on Android: “Download failed
Could not complete operation. Server unavailable.”
During upload with the Desktop app I get error messages in the Nextcloud server log: “Error PHP fread(): read of 8192 bytes failed with errno=21 Is a directory at /data/nextcloud/lib/private/Files/Storage/Wrapper/Encryption.php#861” - When I browse through the server web interface everything seems fine (folders/file names are encrypted but I see all expected entries & matching file sizes).
Thanks again for helping. The last issue might be some Android app bug. My initial problem is resolved.
Edit: Added my current findings to the mentioned E2EE feedback thread: Help test the latest version of E2EE!