Sachverhalt:
A.
A._ und B._ sind die nie miteinander verheiratet gewesenen Eltern von C._ (geb. 2008). Seit der Trennung der Eltern im Jahr 2009 lebt C._ bei der Mutter. Am 16. September 2014 wurde den Eltern die gemeinsame elterliche Sorge über die Tochter erteilt. Den Antrag des Vaters vom 19. Oktober 2015 auf alternierende Obhut wies die Kindes- und Erwachsenenschutzbehörde Bern (nachfolgend KESB) ab. Eine dagegen erhobene Beschwerde des Vaters blieb ohne Erfolg.
B.
Am 9. Dezember 2015 beantragte die Mutter unter anderem, es sei ihr - unter Anpassung der Kinderbelange - zu erlauben, per 1. Februar 2016 zusammen mit ihrer Tochter nach Bonn zu ziehen; der persönliche Verkehr sei neu zu regeln.
Mit Kammerentscheid vom 27. Januar 2016 erteilte die KESB die Zustimmung zum Wechsel des Aufenthaltsortes der Tochter C._ (Ziff. 1), schrieb den Antrag auf Alleinzuteilung einzelner Elemente der elterlichen Sorge ab (Ziff. 2) und regelte den persönlichen Verkehr zwischen Vater und Tochter für die Übergangszeit nach dem Umzug (Ziff. 3). Ferner entzog die KESB einer allfälligen Beschwerde die aufschiebende Wirkung (Ziff. 7).
In der Folge zog die Mutter anfangs Februar 2016 mit dem Kind nach Bonn.
Gegen den Entscheid der KESB erhob der Vater am 22. Februar 2016 Beschwerde beim Obergericht des Kantons Bern als Kindes- und Erwachsenenschutzgericht.
Mit Entscheid vom 23. Juni 2016 trat das Obergericht wegen entfallener Zuständigkeit auf die Beschwerde nicht ein, wobei es mit subsidiärer Begründung ausführte, dass das Rechtsmittel in der Sache abzuweisen gewesen wäre.
C.
Gegen den obergerichtlichen Entscheid hat A._ am 26. August 2016 eine Beschwerde erhoben mit den Begehren um dessen Aufhebung und Rückweisung der Sache zur materiellen Beurteilung, eventualiter um Abweisung des Gesuchs um Zustimmung zum Wechsel des Aufenthaltsortes des Kindes. Mit Schreiben vom 27. September bzw. 3. Oktober 2016 verzichteten das Obergericht und die KESB auf eine Stellungnahme. Mit Vernehmlassung vom 9. Oktober 2016 schloss die Mutter auf Nichteintreten, eventualiter auf Abweisung, soweit Eintreten. Die Angelegenheit wurde am 23. März 2017 an einer öffentlichen Sitzung beraten.

Erwägungen:
1.
Angefochten ist der kantonal letztinstanzliche Entscheid in einer nicht vermögensrechtlichen Zivilsache; dagegen ist die Beschwerde in Zivilsachen grundsätzlich gegeben (Art. 72 Abs. 1, Art. 75 Abs. 1 und Art. 90 BGG).
Das Beschwerderecht ist indes daran geknüpft, dass der Beschwerdeführer ein schutzwürdiges Interesse an der Aufhebung oder Änderung des Entscheides hat (<ref-law>). Ein solches besteht grundsätzlich nur dann, wenn im Zeitpunkt des bundesgerichtlichen Entscheides nach wie vor ein aktuelles und praktisches Interesse an der Gutheissung der Beschwerde besteht (<ref-ruling> E. 1.1 S. 208; <ref-ruling> E. 1.1 S. 93 f.). Nach der bundesgerichtlichen Rechtsprechung zu <ref-law> erschöpft sich das schutzwürdige Interesse nicht darin, dass einzelnen Begehren nicht oder nicht voll entsprochen wurde; erforderlich ist vielmehr, dass der Entscheid über die Beschwerde geeignet ist, dem Beschwerdeführer den angestrebten Erfolg zu verschaffen (<ref-ruling> E. 2 S. 190; <ref-ruling> E. 2b S. 42).
Vorliegend fragt sich, ob ein solches Interesse noch gegeben ist, weil das Kind vor Einreichen des kantonalen Rechtsmittels aufgrund eines vollstreckbaren Rechtstitels, mithin rechtmässig nach Deutschland ausgereist ist und es selbst bei gutheissendem Rechtsmittelentscheid nicht in die Schweiz zurückgebracht werden könnte, weil dieser in Deutschland mangels indirekter schweizerischer Zuständigkeit (dazu E. 2) nicht anerkennbar wäre (vgl. <ref-law>, Haager Kindesschutzübereinkommen, SR 0.211.231.011) und aufgrund des rechtmässigen Wegzuges im Übrigen auch kein widerrechtliches Verbringen des Kindes im Sinn von Art. 3 und 5 HKÜ (Haager Kindesentführungsübereinkommen, SR 0.211.230.02) vorliegt.
Auf das Erfordernis des fortdauernden Interesses wird allerdings ausnahmsweise verzichtet, wenn sich die gerügte Rechtsverletzung jederzeit wiederholen könnte und eine rechtzeitige gerichtliche Überprüfung kaum je möglich wäre (sog. virtuelles Interesse, vgl. <ref-ruling> E. 1.1 S. 208; <ref-ruling> E. 1.1 S. 94). Ein solches macht der Beschwerdeführer mit zutreffender Begründung geltend. Das Hauptthema der Beschwerde ist, ob der Entzug der aufschiebenden Wirkung bei internationalen Wegzugsfällen wegen der mit dem tatsächlichen Wegzug entfallenden schweizerischen Jurisdiktion (dazu E. 2) überhaupt möglich ist. Zwar thematisiert der Beschwerdeführer gerade die Frage der Dringlichkeit der Anordnung nicht, obwohl sie für die Beantwortung des Grundsatzes zentral wäre (dazu E. 4); indes bringt er verschiedene andere in Bezug auf die Grundsatzfrage entscheidende Rügen vor (dazu E. 5 und 6). An der Klärung dieser vom Bundesgericht im Zusammenhang mit dem auf 1. Juli 2014 in Kraft getretenen <ref-law> (Bundesgesetz vom 21. Juni 2013, AS 2014 357) noch nie beantworteten und zwangsläufig auch in künftigen Fällen nie rechtzeitig beantwortbaren Rechtsfragen besteht ein grosses Interesse. Auf die Beschwerde ist nach dem Gesagten einzutreten.
2.
Der Behandlung der betreffenden Fragen ist vorauszuschicken, dass das Obergericht angesichts des erfolgten tatsächlichen Wegzuges des Kindes zu Recht nicht auf die gegen die Wegzugsentscheidung der KESB eingereichte Beschwerde eingetreten ist. Mit dem Wegzug des Kindes in einen anderen Vertragsstaat des Haager Kindesschutzübereinkommens und dortiger Begründung gewöhnlichen Aufenthaltes - vorliegend ohne Weiteres zu bejahen, da der Wegzug mit dem hauptbetreuenden Elternteil erfolgt ist, welcher am Zuzugsort einen neuen Wohnsitz begründet hat (dazu <ref-ruling> E. 4.1 S. 292; <ref-ruling> E. 2.1 S. 4; Urteil 5A_293/2016 vom 8. August 2016 E. 3.1 m.w.H.), und das Kind am neuen Ort eingeschult worden ist - entfällt die internationale Zuständigkeit der schweizerischen Gerichte (<ref-law>; BGE <ref-ruling> E. 2.1 S. 4 m.w.H.), soweit - was der Beschwerdeführer zu Recht nicht behauptet - kein widerrechtliches Verbringen im Sinn von <ref-law> vorliegt; der Wegfall der Entscheidzuständigkeit gilt grundsätzlich auch in Bezug auf das mit einem Rechtsmittel befasste Gericht (<ref-ruling> E. 2.3.1 S. 592; Urteile 5A_622/2010 vom 27. Juni 2011 E. 3 und 4; 5A_131/2011 vom 31. März 2011 E. 3.3.1; BUCHER, in: Commentaire romand, N. 24 zu <ref-law>) und a fortiori für das im Zeitpunkt des Wegzuges noch gar nicht mit einem Rechtsmittel befasste Gericht. Ein in Verletzung der direkten Zuständigkeit gemäss <ref-law> ergangener materieller Entscheid könnte im Vertragsstaat des neuen gewöhnlichen Aufenthaltes auch nicht anerkannt werden (vgl. <ref-law>).
3.
Vorliegend treten verschiedene Grundsätze in Widerstreit. In bestimmten Situationen verlangt das Kindeswohl - welches die Leitmaxime des materiellen Kindesrechts bildet (<ref-ruling> E. 3.4.2 S. 255; <ref-ruling> E. 4.2.4 S. 319; <ref-ruling> E. 5.4 S. 340; <ref-ruling> E. 2.6 S. 491) - nach rascher Entscheidung. Dies darf indes nicht den Anspruch auf Zugang zu einem Gericht untergraben. Auf dieser Ebene ist der Regelungsgegenstand mit der Effektivität des Rechtsschutzes in Einklang zu bringen. Spezifisch für den transnationalen Wegzug des Kindes tritt der Umstand hinzu, dass das Haager Kindesschutzübereinkommen mit Bezug auf das Sorgerecht einschliesslich des Aufenthaltsbestimmungsrechts (vgl. <ref-law>) ein Zuständigkeitsregime aufstellt (vgl. <ref-law>), welches einen Kompetenzwechsel herbeiführt und bewusst von der perpetuatio fori absieht (vgl. LAGARDE, Explanatory Report zum HKsÜ, Rz. 41 f.; Practical Handbook on the Operation of the 1996 Hague Child Protection Convention, Hague Conference on Private International Law 2014, S. 41 [beide Dokumente abrufbar auf der Website der Haager Konferenz www.hcch.net]). Es geht darum, innerhalb des Haager Rechtsraumes die materielle Entscheidkompetenz einem Gericht mit örtlicher Nähe zum aktuellen Aufenthaltsort des Kindes und damit demjenigen Gericht zuzuweisen, welches in der Regel über mehr Sachnähe verfügt (vgl. LAGARDE, a.a.O., Rz. 8 und 37). Dieser Grundsatz ergibt sich indirekt auch aus <ref-law>. Ausnahmen bestehen primär im Zusammenhang mit der Scheidungszuständigkeit (vgl. <ref-law>; Erläuternder Bericht, Rz. 62 ff.). Diese Konstellation interessiert aber vorliegend nicht.
Im Nachfolgenden werden die eingangs genannten Grundsätze in eine wechselseitige Beziehung und Ordnung zu bringen sein. Dabei ist, namentlich auch für die Frage nach dem Zugang zu einem Gericht, dem soeben dargelegten Haager Zuständigkeitsmechanismus besonderes Augenmerk zu schenken.
4.
Der Beschwerdeführer stellt nirgends in Frage, dass sich die KESB auf Art. 314 Abs. 1 i.V.m. <ref-law> und damit auf eine formell-gesetzliche Grundlage gestützt hat. In Fällen, welche keinen Aufschub dulden, ist die Option, einer allfälligen Beschwerde die aufschiebende Wirkung zu entziehen, denn auch keine blosse Möglichkeit, sondern Pflicht (vgl. STECK, in: FamKommentar Erwachsenenschutz, N 7 zu <ref-law>). Gleichzeitig versteht sich aber von selbst, dass der Entzug der aufschiebenden Wirkung eine Dringlichkeit des Vollzuges bzw. vorliegend des Wegzuges voraussetzt. Im Einzelfall ist eine Abwägung der auf dem Spiel stehenden Interessen vorzunehmen (vgl. GEISER, in: Basler Kommentar, N. 7 zu <ref-law>), bei welcher stets auch die Hauptsachenprognose eine Rolle spielt. Was die Besonderheit des vorliegenden Falles anbelangt, so bildet der Verlust der schweizerischen Jurisdiktion bei Auswanderung des Kindes ebenfalls ein für die Abwägung zu berücksichtigendes Kriterium, denn genau deshalb hat der Gesetzgeber die Verlegung des gewöhnlichen Aufenthaltes ins Ausland unabhängig von den konkreten Begebenheiten des Einzelfalles als zustimmungspflichtig erklärt (Botschaft des Bundesrates vom 16. November 2011, BBl 2011 9108).
Der Beschwerdeführer thematisiert indes die - mit dem Stellenantritt der Mutter in Bonn (Arbeitsvertrag ab 1. Februar 2016) begründete - Dringlichkeit nicht, sondern beschränkt sich auf das Vorbringen (dazu E. 5 und 6), bei Auswanderung von Kindern habe die ansonsten einzelfallweise vorzunehmende Interessenabwägung von vornherein zu unterbleiben, weil ein in Anwendung von <ref-law> erlaubender erstinstanzlicher Entscheid von der Rechtsmittelinstanz gar nie überprüft und gegebenenfalls korrigiert werden könne, wenn das Kind zwischenzeitlich im Ausland neuen gewöhnlichen Aufenthalt begründet habe.
5.
Der Beschwerdeführer rügt eine Verletzung von Art. 29a und 30 BV, Art. 6 Ziff. 1 EMRK sowie Art. 14 UNO-Pakt II. Sein Anspruch auf gerichtliche Beurteilung der Wegzugsfrage habe zivilrechtlichen Charakter im Sinn von Art. 6 EMRK und die KESB sei im Kanton Bern kein Gericht im Sinn dieser Bestimmung. Sie sei der Justiz-, Gemeinde- und Kirchendirektion unterstellt, welche auch die Steuerung und Aufsicht über die administrative und organisatorische Führung ausübe. Sodann würden die Mitglieder der KESB nicht auf eine bestimmte Amtsdauer gewählt, sondern der Regierungsrat ernenne diese auf Antrag der Direktion und die Regierungsstatthalter des jeweiligen Verwaltungskreises seien berechtigt, dem Regierungsrat eine Person aus dem Statthalteramt als Mitglied vorzuschlagen. Im Übrigen seien die Verfahren vor der KESB auch nicht öffentlich und sehe das kantonale Gesetz keinerlei Ausstandsregelung vor.
5.1. Im öffentlich beratenen und zur Publikation bestimmten Urteil 5A_738/2016 vom 17. November 2016 hat sich das Bundesgericht in E. 3.3 und 3.4.1 zur Frage, ob die KESB im Kanton Thurgau ein Gericht im Sinn von <ref-law> und Art. 6 Ziff. 1 EMRK ist, in grundsätzlicher Weise und mit vielen Hinweisen auf die bundesgerichtliche und die Strassburger Rechtsprechung geäussert. Es hat zusammengefasst erwogen, dass das urteilende Organ nicht in die ordentliche Gerichtsstruktur eingegliedert, aber organisatorisch und personell sowie nach seinem äusseren Erscheinungsbild unabhängig und unparteiisch sein muss. Dass die Wahl der Mitglieder des betreffenden Organs durch den Regierungsrat statt durch den Grossen Rat bzw. durch das Volk erfolge, genüge für sich allein genommen nicht, um die Eigenschaft als unabhängiges Gericht abzuerkennen. Angesichts der im Kanton Thurgau erfolgenden Wahl der Mitglieder der KESB auf eine Amtsdauer von vier Jahren, der bloss administrativen, nicht aber fachlichen Aufsicht durch den Regierungsrat, der Beschränkung der Zuständigkeit auf die vom Bundesrecht zugewiesenen Bereiche, der Erforschung des Sachverhaltes und der Rechtsanwendung von Amtes wegen ging das Bundesgericht davon aus, dass die KESB im Kanton Thurgau die an ein unabhängiges Gericht zu stellenden Voraussetzungen erfüllt.
5.2. Die Kantone sind unter Vorgabe bundesrechtlicher Minimalanforderungen - Fachbehörde, welche ihre Entscheide grundsätzlich in Dreierbesetzung fällt (vgl. <ref-law>) - in der Ausgestaltung der Kindes- und Erwachsenenschutzbehörden frei; insbesondere entscheiden sie autonom darüber, ob die Behörde als unabhängiges Gericht oder als Verwaltungseinheit konstituiert ist (VOGEL, in: Berner Kommentar, N. 11 zu <ref-law>; WIDER, in: FamKomm Erwachsenenschutz, N. 23 zu <ref-law>). Ob ein kantonales Regime, welches die KESB als Verwaltungseinheit konstituiert, mit Blick darauf, dass die Kindesschutzbehörde von Bundesrechts wegen zur Entscheidung über genuin zivilrechtliche Ansprüche berufen ist, eine restlos überzeugende Lösung darstellt, kann dahingestellt bleiben; anders als noch im Vorentwurf, welcher zwingend die Einrichtung von Fachgerichten vorschreiben wollte, wurde den Kantonen aufgrund der im Vernehmlassungsverfahren vorgetragenen Kritik im Entwurf zur Revision des Vormundschafts- bzw. Erwachsenenschutzrechts bewusst die betreffende Autonomie gewährt (vgl. Botschaft vom 28. Juni 2006, BBl 2006 7004, 7010 f. und 7021).
5.3. In Bezug auf die Organisation und das äussere Erscheinungsbild der KESB im Kanton Bern stechen markante Unterschiede gegenüber der in E. 5.1 beschriebenen Thurgauer Situation ins Auge, und zwar bereits unmittelbar aus dem Entscheid, um welchen es vorliegend geht; dort ist links oben auf der ersten Seite als entscheidende Instanz aufgeführt: "Justiz-, Gemeinde- und Kirchendirektion des Kantons Bern" sowie unmittelbar darunter "Kindes- und Erwachsenenschutzbehörde (KESB) Bern". Dies erweckt gegen aussen den klaren Anschein einer Integration des Entscheidungsträgers in die kantonale Verwaltung. Dass es sich bei der KESB im Kanton Bern nicht nur dem Anschein nach, sondern auch tatsächlich um eine (dezentrale) Verwaltungseinheit handelt, ergibt sich aus Art. 18 Abs. 2 lit. c KESG/BE (BSG 213.316), wonach die Justiz-, Gemeinde- und Kirchendirektion gegenüber den KESB-Präsidien die Vorgesetztenfunktion in personalrechtlichen Belangen ausübt, sowie aus Art. 4 Abs. 1 KESV/BE (BSG 213.316.1), welcher auf die Grundsätze der Verordnung für die Organisation und Steuerung der dezentralen Verwaltung der JGK (OSDV/BE, BSG 152.322.1) verweist. Was die Entscheidfindung anbelangt, sind die KESB gemäss Art. 2 Abs. 3 KESG/BE unabhängig. In die gleiche Richtung deutet der bezüglich Wahl, Organisation und Kompetenzen erfolgende Verweis in Art. 1 Abs. 2 KESG/BE auf das GSOG/BE (BSG 161.1), welches in Art. 4 die Unabhängigkeit der Gerichtsbehörden und der Staatsanwaltschaft deklariert. In gewissem Widerspruch dazu stehen jedoch Art. 4 Abs. 3 lit. a, f und g KESV/BE, wonach das Kantonale Jugendamt (KJA) in eigener Verantwortung die fachliche Beratung und Unterstützung der KESB wahrnimmt, Richtlinien sowie Weisungen erlässt und die Mitarbeitergespräche mit den KESB-Präsidien führt. Angesichts dieser schillernden Rechtslage ist zweifelhaft, ob die KESB im Kanton Bern in fachlicher Hinsicht bzw. bei ihrer Entscheidfindung wirklich vollständig unabhängig ist. Jedenfalls in personeller Hinsicht ist nach der aktuellen Rechtslage ein Subordinationsverhältnis nicht wegzudiskutieren. Klar ist sodann die organisatorische Einbindung, indem die KESB im Kanton Bern als dezentrale Verwaltungseinheit ausgestaltet ist.
5.4. Vor diesem Hintergrund ist nicht zu erkennen, inwiefern die KESB im Kanton Bern als unabhängiges Gericht im Sinn von <ref-law> und Art. 6 Ziff. 1 EMRK gelten könnte. Gestaltet ein Kanton die betreffende Behörde als Verwaltungseinheit aus, bedeutet das aber für sich genommen noch keine Verletzung der Rechtsweggarantie gemäss <ref-law>. Diese stellt keine unmittelbaren Anforderungen an die Gerichtsorganisation (WALDMANN, in: Berner Kommentar, N. 16 zu <ref-law>), sondern besteht einzig darin, dass die Rechtsstreitigkeit wenigstens einmal durch eine richterliche Behörde beurteilt wird (statt vieler: WALDMANN, a.a.O., N. 13 zu <ref-law>). Dies ist vorliegend der Fall, weil eine Beschwerdemöglichkeit an das mit uneingeschränkter Kognition ausgestattete (vgl. Art. 314 Abs. 1 i.V.m. <ref-law>) Obergericht des Kantons Bern bestand und dessen Entscheid an das Bundesgericht weitergezogen werden kann. Insbesondere liegt auch keine Konstellation vor, in welcher über die Rechtsweggarantie hinaus von Verfassungs (vgl. <ref-law>) oder Gesetzes wegen bereits in erster Instanz zwingend ein Gericht entscheiden müsste.
5.5. Im vorliegenden Fall ergibt sich sodann, dass der Beschwerdeführer nicht nur virtuell, sondern tatsächlich Zugang zu einem Gericht hatte (vgl. E. 6.3) und auch weiterhin hat (dazu sogleich).
Abgesehen davon, dass der angefochtene Entscheid subsidiär eine materielle Begründung enthält (dazu E. 7), darf vorliegend der in E. 2 und 3 beschriebene Haager Mechanismus nicht ausser Acht gelassen werden. Wie gesagt will das Haager Kindesschutzübereinkommen innerhalb der Vertragsstaaten für alle Sorgerechtsbelange einschliesslich des Aufenthaltsbestimmungsrechts den Zugang zu einer sachnahen Entscheidinstanz sicherstellen, was in bewusster Wertung durch Verzicht auf das Prinzip der perpetuatio fori geschieht. Durch die Ratifizierung des betreffenden Übereinkommens schaffen die Vertragsstaaten einen einheitlichen Rechtsraum, wobei die staatsvertraglich erfolgende Zuweisung der Zuständigkeiten notwendigerweise mit dem betreffenden Verzicht der Vertragsstaaten auf eigene konkurrenzierende Zuständigkeiten einhergeht (vgl. LAGARDE, a.a.O., Rz. 6). Es verhält sich nicht anders als beispielsweise beim Lugano-Übereinkommen, wo dem Kläger ebenfalls zugemutet wird, an den in <ref-law> festgelegten Gerichtsständen und damit gegebenenfalls im Ausland zu klagen. Darin liegt keine unzulässige Beschränkung der Rechtsweggarantie.
Vorliegend ist der Zuständigkeitsverlust gemäss <ref-law> eo ipso als Folge des Wegzuges eingetreten. Dass aber die Rechtsfolge nicht gewissermassen zu einer Voraussetzung für die materielle Wegzugsentscheidung bzw. zu deren zentralem Entscheidungskriterium gemacht werden kann, hat das Bundesgericht bereits im Zusammenhang mit der analogen Fragestellung festgehalten, ob bei gegebener Dringlichkeit über die Wegzugsfrage im Rahmen von vorsorglichen Massnahmen entschieden werden darf (vgl. Urteil 5A_306/2016 vom 7. Juli 2016 E. 3.2.2).
Der Beschwerdeführer macht nicht geltend, dass er innerhalb des von den Vertragsstaaten durch die Ratifikation des HKsÜ geschaffenen Rechtsraumes - vorliegend in Deutschland - kein im Sinn von Art. 6 Ziff. 1 EMRK unabhängiges Gericht anrufen könnte, welches über die Fragen des Sorgerechts einschliesslich des Aufenthaltsbestimmungsrechts und des persönlichen Verkehrs materiell entscheiden würde. Es ist denn auch nicht zu sehen, inwiefern der Zugang zu einem Gericht für die betreffenden Fragen bei einem Wegzug des Kindes in einen anderen Vertragsstaat des Haager Kindesschutzübereinkommens nicht weiterhin lückenlos bestehen würde; vielmehr ist dies gerade das zentrale Anliegen des Übereinkommens.
6.
Der Beschwerdeführer macht eine Verletzung von Art. 13 EMRK i.V.m. Art. 8 EMRK und <ref-law> geltend. Die entzogene aufschiebende Wirkung habe zur Folge gehabt, dass die Mutter kurz nach Eröffnung des Entscheides der KESB die Schweiz zusammen mit dem Kind verlassen habe. Als Folge davon sei das Obergericht auf seine fristgerechte Beschwerde nicht eingetreten. Zum einen hätte die KESB ihn in der Rechtsmittelbelehrung auf diesen Umstand hinweisen müssen. Sodann sei es ihm nicht zumutbar gewesen, während der laufenden 30-tägigen Rechtsmittelfrist zu prüfen und zu kontrollieren, ob und wann seine Tochter effektiv nach Deutschland übersiedle; er sei darüber von der Mutter nicht informiert worden.
6.1. Nach Art. 13 EMRK hat jede Person, die in ihren konventionsmässig anerkannten Rechten oder Freiheiten verletzt worden ist, das Recht, bei einer innerstaatlichen Instanz eine wirksame Beschwerde zu erheben, auch wenn die Verletzung von Personen begangen worden ist, die in amtlicher Eigenschaft gehandelt haben. Das Recht auf wirksame Beschwerde ist ein akzessorisches Recht. Eine Verletzung von Art. 13 EMRK kann nur in Verbindung mit einer materiellen Garantie der EMRK gerügt werden, was im vorliegenden Fall (Art. 8 EMRK i.V.m. <ref-law>) zutrifft. Mit Art. 13 EMRK sollen die Konventionsrechte der Sache nach innerstaatlich garantiert werden (vgl. BREUER, in: Karpenstein/Mayer, EMRK Kommentar, N. 25 zu Art. 13 EMRK). Im Vordergrund steht die Frage, was eine "wirksame Beschwerde" bedeutet. Nach der Rechtsprechung muss die Beschwerde sowohl rechtlich als auch tatsächlich wirksam sein (vgl. EGMR Nr. 22689/07 vom 18. Dezember 2012 in Sachen de Souza Ribeiro gegen Frankreich § 78; GRABENWARTER/PABEL, Europäische Menschenrechtskonvention, 6. Aufl. 2016, § 24 N. 197; BREUER, a.a.O., N. 42 zu Art. 13 EMRK), indem sie die vermeintliche Verletzung beziehungsweise ihr Andauern verhindert (vgl. EGMR Nr. 29400/05 vom 19. Juni 2012 in Sachen Kommunistische Partei Russlands gegen Russland § 82).
6.2. Zunächst lässt sich aus Art. 13 EMRK kein Anspruch darauf ableiten, dass in der Rechtsmittelbelehrung hinzuweisen wäre, dass das Obergericht nach erfolgtem Wegzug des Kindes in einen anderen Vertragsstaat der Kindesschutzübereinkommens auf die Beschwerde nicht eintreten werde. Die Rechtsmittelbelehrung hat das Rechtsmittel, die Frist und die Rechtsmittelinstanz zu bezeichnen und sich allenfalls zu den Begründungsanforderungen zu äussern (vgl. statt vieler: Urteil 8F_12/2014 vom 15. April 2015 E. 4.3). Hingegen kann es der Entscheidinstanz von vornherein nicht zustehen, sich in der Rechtsmittelbelehrung darüber zu äussern, wie der Entscheid der Rechtsmittelinstanz lauten wird.
6.3. Das weitere Vorbringen des Beschwerdeführers, es sei ihm nicht zumutbar gewesen zu überprüfen, ob das Kind während der laufenden Rechtsmittelfrist nach Deutschland wegziehe, soll offensichtlich insinuieren, dass unbesehen um die konkrete Ausgangslage die volle 30-tägige Rechtsmittelfrist habe ausgeschöpft werden dürfen, um die notwendigen Vorkehrungen zu treffen. Solches lässt sich aber aus Art. 13 EMRK nicht ableiten.
In tatsächlicher Hinsicht ist offensichtlich, dass der Beschwerdeführer aufgrund der Vorbringen der Mutter im erstinstanzlichen Verfahren (Arbeitsstelle in Bonn per 1. Februar 2016) wusste, dass der Wegzug unmittelbar bevorstehen würde. Genau dies war ja der Grund für den Entzug der aufschiebenden Wirkung, wie unmittelbar aus der Begründung des Entscheides der KESB hervorgeht. Sodann ergibt sich die entsprechende Anordnung klar aus dem Dispositiv des Entscheides. Dessen Kenntnisnahme bei Erhalt sowie die Einleitung der sich aufgrund des Dispositivs ergebenden notwendigen Schritte gehören zur sorgfältigen anwaltlichen Tätigkeit, jedenfalls soweit die Dringlichkeit offensichtlich und rasches Handeln objektiv möglich ist. In diesem Zusammenhang ist zu betonen, dass es keineswegs notwendig gewesen wäre, innerhalb weniger Tage die vollständige Beschwerde einzureichen. Vielmehr hätte es genügt, den Entscheid anzufechten, mit kurzer Begründung superprovisorisch die Erteilung der aufschiebenden Wirkung zu verlangen und eine einlässliche Beschwerdebegründung innerhalb der zur Verfügung stehenden 30-tägigen Frist in Aussicht zu stellen. Das Einreichen einer wirksamen Beschwerde wäre deshalb im vorliegenden Fall ohne Weiteres möglich gewesen.
6.4. Schliesslich darf das bereits mehrfach beschriebene Haager Zuständigkeitsregime auch im Zusammenhang mit der Frage nach der effektiven Rechtsmittelmöglichkeit nicht ausser Acht gelassen werden. Dem Beschwerdeführer steht nach dem Gesagten am neuen Aufenthaltsort des Kindes der Zugang zu einem Gericht mit dortigem Instanzenzug offen. Zwar ist dies selbstredend nicht im technischen Sinn ein Rechtsmittel gegen den erstinstanzlichen schweizerischen Entscheid; wohl aber kann von einer funktionalen Rechtsbehelfsmöglichkeit gesprochen werden, indem der Beschwerdeführer in Deutschland die identische Sachfrage - nämlich die Frage nach dem geeigneteren Aufenthaltsort des Kindes unter der Hypothese, dass die Mutter nicht mehr in Bern, sondern in Bonn lebt (vgl. dazu BGE <ref-ruling> E. 2.6 S. 492) - einem Gericht unterbreiten und diesbezüglich den Instanzenzug durchlaufen kann.
7.
Über die Nichteintretenserwägungen hinaus hat das Obergericht seinen Entscheid subsidiär auch materiell begründet, und zwar dahingehend, dass die Mutter die hauptbetreuende Person ist und es im Interesse des Kindes liegt, wenn es mit ihr nach Deutschland zieht. Im Übrigen verneinte das Obergericht die Ansicht des Beschwerdeführers, der Umzug diene primär dazu, ihn aus dem Leben des Kindes zu verdrängen; es hielt fest, dass die Mutter in Bonn aufgewachsen sei, dort Verwandte und Freunde sowie eine neue Arbeitsstelle habe, so dass der Umzug offensichtlich aus sachlichen Gründen erfolge.
Der Beschwerdeführer kritisiert die materielle Begründung des Obergerichtes als oberflächlich; gemäss BGE <ref-ruling> E. 2.3 S. 486 seien im Sinn der Washingtoner Erklärung die verschiedenen Parameter im Rahmen einer umfassenden Auslegeordnung zu prüfen und zu beantworten. Insbesondere sei gemäss BGE <ref-ruling> E. 2.7 S. 495 auch die Umteilung des Kindes in Erwägung zu ziehen, wenn ein Elternteil offensichtlich nur deshalb wegziehe, um es dem anderen zu entfremden. Ferner habe sich das Obergericht nicht mit der Stellungnahme der Beiständin vom 6. Januar 2016 auseinandergesetzt, wonach das Kind bei einem Aufenthaltswechsel all seine Freunde und Bekannten sowie seinen Therapeuten und sein gesamtes vertrautes Umfeld in der Schweiz verliere und sich in einem unbekannten Umfeld neu zurechtfinden müsste.
In erster Linie wird damit eine Verletzung der Begründungspflicht als Teilgehalt des rechtlichen Gehörs geltend gemacht. Dies setzt jedoch eine substanziierte Verfassungsrüge, nämlich die Rüge der Verletzung von <ref-law> voraus, wofür das strenge Rügeprinzip gemäss <ref-law> gilt (zu den diesbezüglichen Rügeanforderungen siehe <ref-ruling> E. 1.4 S. 176). Dem vermögen die weder der Form noch dem Inhalt nach als Verfassungsrüge, sondern in rein appellatorischer Weise vorgetragenen Ausführungen nicht ansatzweise gerecht zu werden.
Im Übrigen war der Wegzug auch von der Sache her klarerweise zu erlauben und insbesondere steht diese Erlaubnis entgegen den Ausführungen des Vaters nicht in Widerspruch, sondern in Übereinstimmung mit der einschlägigen bundesgerichtlichen Rechtsprechung zu <ref-law>. Im Leitentscheid BGE <ref-ruling> hat das Bundesgericht festgehalten, dass in einem ersten Schritt gerade nicht - im Sinn der Washingtoner Erklärung (dazu E. 2.3 S. 486) - eine allgemeine Abwägung zwischen den Interessen aller Beteiligten vorzunehmen ist, sondern aufgrund einer bewussten Entscheidung des Gesetzgebers im Rahmen der parlamentarischen Beratung von <ref-law> (dazu E. 2.4 S. 487 f.) ein jeder Elternteil frei ist, um- oder wegzuziehen (E. 2.5 S. 488 ff.), und in einem zweiten Schritt unter der Hypothese des Wegzuges der geeignetere Aufenthaltsort des Kindes zu klären ist (E. 2.6 S. 491 f.), namentlich anhand von Kriterien wie Stabilität der Verhältnisse, Erziehungsfähigkeit sowie Betreuungsmöglichkeit der Eltern, Alter und Äusserungen sowie Bedürfnisse des Kindes, dessen Bezug zum alten und neuen Ort, sprachliche Integration u.a.m.
Für den vorliegenden Fall ergibt sich aus den Entscheiden der KESB und des Obergerichts, dass das Begehren des Vaters um alternierende Obhut angesichts des in diesem Zusammenhang in Auftrag gegebenen Ergänzungsgutachtens vom 29. Juni 2015, welches der Mutter volle und dem Vater eine eingeschränkte Erziehungsfähigkeit attestierte, mit Entscheid der KESB vom 2. September 2015, bestätigt durch das Obergericht mit Entscheid vom 21. Januar 2016, abgewiesen wurde und das Kind deshalb weiterhin zur Hauptsache von der Mutter betreut wird, wobei der Vater in der Schweiz über ein erweitertes Besuchsrecht verfügte. Weiter ergibt sich, dass eine enge Beziehung zu den in Gehdistanz lebenden Grosseltern in Bonn besteht und auch der Pate in dortiger Nähe wohnt, dass die Mutter in Bonn eine angemessene Wohn- und Betreuungslösung gefunden hat, während der Vater für den Fall eines Verbleibens des Mädchens in der Schweiz keine Lösung aufgezeigt bzw. einzig mit Schreiben vom 22. Dezember 2015 abstrakt festgehalten hat, mit Hilfe der Grossmutter die Betreuung problemlos sicherstellen zu können, dass das Kind an beiden Elternteilen hängt, jedoch die Mutter seine wichtigste Bezugsperson ist und es gemäss Ergänzungsgutachten altersentsprechend entwickelt und verhaltensunauffällig ist.
Dass bei einem Umzug auf grössere Distanz die Beziehung zum alten Ort bei einem Kind im Alter von C._ relativ rasch verblasst und die Therapie nicht mit dem bisherigen Therapeuten fortgesetzt werden kann, versteht sich von selbst und ergibt sich nicht erst aus dem Bericht der Beiständin, welchen das Obergericht im Unterschied zur KESB nicht ausdrücklich zitiert hat. Indes behauptet auch der Vater nicht, dass die Therapie in Bonn nicht fortgeführt werden könnte. Sodann sprechen die einschlägigen Kriterien (Erziehungseignung, Betreuungskontinuität) dafür, dass es im besseren Interesse des Kindes ist, mit der Mutter nach Bonn zu ziehen, als zum Vater umplatziert zu werden. Im Übrigen lässt sich entgegen den Vorbringen des Beschwerdeführers auch nicht von einer gefährdenden Entwurzelung des Kindes sprechen; es verbleibt im gleichen Sprachraum und wird künftig in einem ihm aus Besuchen bereits bekannten und in Kürze vertrauten Umfeld leben (Grosseltern, Götti, Freundeskreis der Mutter und bald auch eigene Schulfreundinnen). Ferner bleibt es auch in der vorliegenden Beschwerde bei der abstrakten Behauptung, die Mutter wolle ihm das Kind entfremden und der Wegzug beruhe deshalb nicht auf sachlichen Motiven; dem stehen die von der KESB und dem Obergericht getroffenen, für das Bundesgericht verbindlichen gegenteiligen Sachverhaltsfeststellungen (<ref-law>) entgegen, vor deren Hintergrund die in spezifischen Fallkonstellationen indizierte Überprüfung einer Umplatzierung (vgl. BGE <ref-ruling> E. 2.7 S. 495) - vorliegend zum bisher nicht betreuenden und gemäss Gutachten für die Betreuung auch weniger geeigneten Vater - nicht entfernt zur Debatte stehen kann.
Dem kantonalen Rechtsmittel konnte somit in der Sache kein Erfolg beschieden sein und die dahingehenden subsidiären materiellen Erwägungen des Obergerichtes verletzen kein Bundesrecht. Erneut sei aber betont, dass es sich dabei um eine materielle Eventualbegründung handelte und das Obergericht auf die Berufung richtigerweise nicht eingetreten ist, weil es keinen materiellen Entscheid fällen durfte und ein solcher in Deutschland auch nicht anerkannt werden dürfte (vgl. dazu E. 2).
8.
Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen ist, soweit auf sie eingetreten werden kann. Der Beschwerdeführer wird somit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der KESB Bern und dem Obergericht des Kantons Bern schriftlich mitgeteilt.
Lausanne, 23. März 2017
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Möckli