As a German, I think this is a myth. Black bread/pumpernickel are only to be found in some regions of Germany, and even there, it’s not very popular among people younger than retirement age.
you can still find it in the south of germany and in austria, but there it is usually not freshly baked but sliced and packaged.
Sure, the assortment of wheat based breads is larger and very small shops might not have it at all, but overall it is pretty common (the two bakeries within a 100m radius of my place both have it). However, if you are looking for top quality black bread you might be out of luck with your closest bakery, but should find a shop within a few kilometers. Just to give one example:
'Bäckerei Junge' is one of the common bakeries: https://www.jb.de/geschaeftefinder/
And one of their high quality black breads is the 'Kerne & Saaten': https://www.jb.de/produktfinder/aus/hamburg/in/brot/produkt/...