Finally, I fixed the Phoca Download issue. I realized that 3.X version was installed in Joomla 4 though I uninstalled all Phoca extensions prior to Joomla 4 upgrade and though I installed Phoca Gallery and Phoca Download via Joomla's internal Extension Library.
So I manually updated Phoca Download to 4.0.2 in Joomla 4 and this worked.
Nevertheless, I threw away my test site again and did the whole migration/upgrade process again to be sure (this time I installed all Phoca extensions manually and not via Joomla Extension Library).
Phoca Download is now fine.
Phoca Gallery again or still did not show any categories below the top-level categories:
https://test.ulc-moedling.at/medien/ulc-fotos/galerie
Backend shows the category hierarchy.
Backend --> Components --> Phoca Gallery --> Control Panel --> Options --> Categories View -->
Display Subcategories=No
Display Empty Categories=Yes
Both set as in Joomla 3 production site and as you suggested.
All caches are disabled: System Configuration/Server: Caching Disabled
Joomla Page Cache Extension: Disabled
JCH Cache extensions: Disabled
Caching in Phoca Gallery & Phoca Download: Disabled
Cache cleared in Joomla and Shift-Reload in Browser.
But I fixed even that:
I had to set "Category View" --> "Display Categories in Category View" to Yes to display the categories. My Joomla 3 production site shows this setting set to No and it works as expected. Strange difference, right?
Btw, thank you for German translations Benno. I translated AcyMailing to German.