Ungewollter Zusatzvertrag im o2 Shop

Mir ist folgendes passiert, ich war vor 3 Tagen mit meiner Freundin in einem O2 Shop.
Wir wollten eine Vertragsverlängerung und ein neues Handy dazu, daraufhin hat der Herr in dem O2 Shop uns ein Angebot gemacht das sich eigentlich ganz gut anhörte. Als wir gerade dabei waren den O2 Shop zu verlassen, ist mir in der O2 App ein neuer Vertrag aufgefallen der sich free s Online (2019) nennt. Daraufhin fragte ich den Herrn was genau dieser Vertrag dar stellen soll. Er antwortete mir das sei die Vertragsverlängerung von meinem ursprünglichen Tarif Free M Boost, diese würde in 24 Stunden umgestellt werden und der Freee M Boost würde verschwinden und durch den Free S Online ersetzt werden. Am nächsten Tag stand der Vertrag aber immer noch drin, somit habe ich bei der Hotline angerufen und nachgefragt, eine Dame teilte mir mit es wurde eine Vertragsverlängerung gemacht und ein neuer Vertrag. Dann schaute ich noch einmal in den Vertrag der mir mitgegeben wurde, in diesem handelte es sich nur um die Verlängerung meinesFree M Boost allein in der Vetragsverlängerung wurde uns nichts mittgeteilt von folgenden Optionen die dazu gebucht worden sind
02 TV L 9,99€, Games flat 4,99€,Napster Music flat 7,99€, 02 Protect Complete flex 4,99€ und eine 02 Cloud flex für 4,99€ , diese sind zwar im ersten Monat kostenlos danach kosten diese aber eine Menge Geld, wenn man diese nicht rechtzeitig kündigt. Als ich mir dann noch einmal die "Werbegeschenke" ansah die der Herr in die Tüte geworfen hat, fiel mir eine lose Simkarte auf. Daraufhin rief ich noch einmal die Hotline von o2 an, die Dame erklärte mir das wäre die Simkarte zu dem von mir nicht gewollten O2 Vertrag mit genau denselben Optionen wie oben schon beschrieben,der dort abgeschlossen wurde ohne mein wissen. Am darauffolgenden Tag fuhren wir noch einmal in den O2 Shop, der Herr war leider nicht gesprächsbereit, da meine Freundin sich mit dem verkaufen von Verträgen auskennt und ihn damit konfrontierte, berief dieser sich darauf wir sollen den Laden verlassen und er würde dieses mit seinem Filialleiter klären, da er selber diesen Vertrag nicht widerrufen kann. Daraufhin setzte sich meine Freundin noch einmal mit der 02 Holtline in Verbindung, diese bestätigte ihr dann das er es doch könne. Somit sind wir wieder in den o2 Shop und meine Freundin bat ihn um etwas schriftliches das dieses Anliegen bearbeitet wird der O2 Shop Mitarbeiter wollte dieses aber leider nicht aushändigen, nach 2 Stunden Diskussion sagte er ganz frech zu meiner Freundin, ich möchte nicht mehr mit ihnen sprechen ich möchte mit dem Vertragsinhaber sprechen. Da ich aber in diesem Fall daneben stand stellte sich für mich kein Problem dar, das er mit meiner Freundin spricht. Jedenfalls war er dann bereit ein Ticket zu erstellen, als sie dann um eine Unterschrift unter diesem Ticket bat sagte er, er würde dieses nicht unterschreiben. Daraufhin folgte wieder eine Diskussion von einer halben Stunde bis er es letztendlich doch unterschrieben hat. Am drauffolgenden Tag riefen wir wieder bei der Hotline an, dieses Ticket das er da erstellt hat gibt es nicht, der Vertrag wurde nicht widerrufen er existiert immer noch. Wir waren bis heute zufriedene O2 Kunden, haben all unsere Verträge bei 02. Leider spielen wir durch diesen Mitarbeiter mit dem Gedanken all unsere Verträge bei 02 zu kündigen. Wir sind maßlos enttäuscht.
Was genau können wir tun?
An wen kann man sich wenden ?