Some update:
I reverted the Phone to Stock OS, but this also didn't help. Then I found this Thread here in German: https://support.google.com/pixelphone/thread/175566419/pixel-6a-mit-esim-fehler-android-13?hl=de
(I should do more research in my language :-D)
Several customers of Deutsche Telekom (largest carrier here in Germany) that had a Pixel 6a were affected. The problems occured there in August and September 2022. It seems that in case the eSIM does have a profile from Deutsche Telekom and an update from Android 12 to Android 13 happen (which includes an update of the eSIM Firmware) bricks the eSIM forever. According to information in the thread, Google replaces these phones.
I think I was not affected in the past, as GrapheneOS did not ship firmware updates of the eSIM prior to 2023040400. It seems to work well, when the firmware update happens when no Deutsche Telekom profile is installed and when the profile is put on the eSIM afterwards.
Overall something that makes me thoughful about realibity of modern tech. I mean, how can it be, that installing the official firmware image to the eSIM module just bricks the chip when the eSIM profile of a large european carrier is installed there? It is not GrapheneOS projects fault, as they only forward the firmware blob.