Hi Jonas!
I haven't had to deal with special characters much, personally, but here's how I look at this. It's going to be most important that your website and your Google My Business page match up - so, it sounds like Google is supporting your special character, so be sure your website is branded that way, too. As for your other citations, I do feel some concerns. You may need to stick to building citations only on those directories that support your special character, or what you will end up with is a bunch of citations that are sharing your phone number, address and website URL, but not your name.
Unfortunately, even if you do stick to building citations only on platforms which support the special character, you are likely to run into a problem because of the way data is shared around the local ecosystem. For example, if you create a citation on golocal and they do accept your character, but they then push that data to das ortliche, and this platform doesn't support the character, it could automatically change the N°1 to No1, meaning that citation inconsistency could end up being auto-generated around the web for the business, simply because of the way data is shared (see: https://moz.com/learn/local/local-search-data-europe). So, basically, I think you're going to have NAP inconsistencies no matter what you do here.
Is it a big enough problem for the business to consider re-branding? That really depends on how well their business is already known. If they aren't well-known, a re-brand might make sense.