Для начала — в любом, они все одинаковые. Можете взять Sparkasse или один из банков CashGroup чтоб меньше проблем с поиском банкомата. Когда у вас будут доходы и финансовые операции, разберетесь и поменяете.

Дождитесь пока у вас будет Fiktionsbescheinigung и принесите этот документ в банк дополнительно. Если банку этого мало, пойдите в другой банк.

С 24.05.2022 можно обменять в немецких банках до 10.000 гривн на взрослого по курсу Bundesbank, см. https://www.bundesfinanzministerium.de/Content/DE/Pressemitteilungen/Finanzpolitik/2022/05/2022-05-23-umtauschprogramm-startet.html

Проще всего — положить на свой счет в банке. См. также 💸У меня есть наличные доллары, где в Нюрнберге их поменять на евро?