Можете попытаться найти другой банк (я рекомендую кого-то из больших - сбер, альфу, втб), если повезет то комиссия будет в районе 15-20 евро. Можно также попробовать оплатить штраф через интернет-банкинг, если он в вашем банке есть.

Антон выше правильно сказал - если хочется минимумом обойтись, то ищете знакомых в Германии/едущих в Германию и просите их оплатить.