Today a short update:
I wasn't able to reach the responsible clerk, but I did get in touch with a colleague at the land registry office. It indeed seems that based on aerial photographs, it was determined that besides the already marked garage, there is another building. Our metal garage! This must also be recorded. Typical German thoroughness ;) .
The costs depend on the year of construction. The older, the cheaper. We can expect 300-400€. That's quite something! An inground pool is excluded; it really only concerns buildings. It also doesn't matter whether a permit exists or if the construction is permit-free.
By the way, several other homeowners in our area are also affected.