прийдется уходить в бумажную волокиту

Во-первых, необходимости писать письма никакой нет на данном этапе, можно просто прийти подготовленными, знать ссылки на законы, и на хорошем немецком потребовать исполнения своих прав. Этого может быть достаточно. Может быть, вообще другой сотрудник попадется, пограмотнее. Если нет, требовать начальства.

Во-вторых, волноваться Вам принципиально не о чем, Ваше пребывание в Германии УЖЕ легально, оно Вам гарантировано директивой ЕС и FreizugG, и вытекает исключительно из Ваших отношений с гражданином ЕС, проживающим в Германии по FreizugG, а не из решений АБХ. Конечно, есть куча других законов, регулирующих проживание людей в Германии (в т.ч. и граждан Германии), такие как обязанность иметь прописку и страховку, и без Aufenthaltskarte тяжеловато может быть тяжеловато полноценно в Германии жить, а тем более выезжать из Германии. И эту проблему решать Вам, естественно надо. Подать заявление - это главный шаг. И, конечно, его можно и нужно подать письменно, per Einschreiben, это сэкономит Вам время и нервы. Тем самым, Вы свою проблему по крайней мере на текущий момент переложите на плечи АБХ, это уже они обязаны будут выдать Вам АК в течение 6 месяцев, а Вы свои обязанности на данном этапе выполните полноценно. Более того, даже если какую-то глупость ответят, что вряд ли, но возможно, то Вы с нами текстом письма поделитесь, и мы подскажем уже конкретно, что делать дальше. С этим устным общением всегда сложности - они Вас не поняли, Вы их не поняли, в итоге сломанный телефончик получается.