Sachverhalt:
A. Die Ehe von A._ und B._, beide deutsche Staatsangehörige, wurde mit Urteil des Amtsgerichts Starnberg (Deutschland) vom 1. Oktober 2007 geschieden. Die gemeinsame elterliche Sorge über die beiden Kinder C._ (geb. 1999) und D._ (geb. 2003) wurde vereinbarungsgemäss beibehalten. B._ wurde berechtigt erklärt, mit den Kindern in die Schweiz zu ziehen. Gemäss der Umgangsregelung (d.h. der Regelung des Besuchsrechts) erhielt A._ im Wesentlichen das Recht, die Kinder jedes zweite Wochenende ab Freitag nach der Schule bis Sonntagabend zu sich zu nehmen. Die Ferien sollten hälftig und die Feiertage Pfingsten, Ostern, Weihnachten und Silvester im jährlichen Wechsel aufgeteilt werden. A._ wurde schliesslich verpflichtet, Unterhaltsbeiträge für die Kinder zu leisten, wobei die Parteien vereinbarten, dass es bei der bestehenden Regelung bleiben solle. Damit bezogen sich die Parteien auf das Urteil des Oberlandesgerichts München vom 13. Juni 2005, in dem die von A._ im Rahmen des Trennungsunterhalts für die Kinder zu leistenden Unterhaltsbeiträge festgelegt worden waren.
B. Am 29. September 2010 verlangte B._ vom Bezirksgericht Affoltern, ihr in Abänderung des Scheidungsurteils des Amtsgerichts Starnberg das alleinige Sorgerecht über die beiden Kinder C._ und D._ einzuräumen, das Besuchs- und Ferienrecht neu zu regeln, den Kindern einen Beistand zur Überwachung der Ausübung des Besuchsrechts zu ernennen und die Unterhaltsbeiträge mit Wirkung ab 4. Februar 2010 angemessen zu erhöhen.
Das Bezirksgericht verfügte eine Prozessbeistandschaft für die beiden Kinder und hörte sie am 13. Juli 2011 bzw. 11. August 2011 an.
Mit Urteil vom 21. Dezember 2011 änderte das Bezirksgericht das Scheidungsurteil ab. Es stellte die beiden Kinder unter die elterliche Sorge von B._. Während das Besuchs- und Ferienrecht für D._ im Wesentlichen unverändert belassen wurde, gewährte es für C._ vorerst kein Ferienrecht und bloss ein reduziertes Besuchsrecht (an jedem zweiten Wochenende entweder am Samstag oder Sonntag). Für beide Kinder sollten die Feiertage Pfingsten, Ostern, Weihnachten und Silvester weiterhin im jährlichen Wechsel aufgeteilt werden. Für den Fall, dass sich die Eltern über die Aufteilung der Feiertage nicht einigten, traf das Bezirksgericht eine Ersatzregelung. Die Kinderunterhaltsbeiträge setzte es wie folgt fest: für C._ monatlich Fr. 1'300.-- ab 4. Februar 2010 bis 30. April 2012 und danach Fr. 1'615.-- bis zum ordentlichen Abschluss einer angemessenen Ausbildung; für D._ monatlich Fr. 1'300.-- ab 4. Februar 2010 bis Ende Februar 2015 und danach Fr. 1'615.-- bis zum ordentlichen Abschluss einer angemessenen Ausbildung. Die Schul- und Berufskosten der Kinder wurden B._ im Umfang von zwei Fünfteln und A._ im Umfang von drei Fünfteln auferlegt. Für C._ wurde eine Beistandschaft gemäss <ref-law> zur Förderung und Organisation des Kontakts zwischen ihr und A._ errichtet.
C. Am 1. Februar 2012 erhob A._ gegen das Urteil des Bezirksgerichts Berufung an das Obergericht des Kantons Zürich. Er beantragte die Aufhebung des angefochtenen Urteils und die Abweisung der Klage. B._ und die Prozessbeiständin der Kinder widersetzten sich der Berufung. In der Duplik beantragte B._ zudem, auch für D._ einen Beistand einzusetzen und A._ anzuweisen, mit den Kindern altersgerechte Gespräche zu führen und ihnen gegenüber herabwürdigende Bemerkungen über B._ und deren Familie zu unterlassen. Am 27. September 2012 wurde C._ erneut angehört.
Mit Urteil vom 6. Februar 2013 stellte das Obergericht C._, nicht hingegen D._, unter die elterliche Sorge von B._. In Bezug auf C._ wurde A._ ein Besuchsrecht an jedem vierten Wochenende von Samstag, 9.30 Uhr, bis Sonntag, 19.00 Uhr, eingeräumt und in den Sommerferien ein Ferienbesuchsrecht von mindestens einer Woche. Die Feiertage Pfingsten, Ostern, Weihnachten und Silvester seien im jährlichen Wechsel aufzuteilen. Wenn sich die Eltern nicht einigen, solle A._ berechtigt sein, C._ in den geraden Jahren von Karfreitag bis Ostermontag und vom 25. bis 26. Dezember sowie in den ungeraden Jahren von Pfingstsamstag bis Pfingstmontag und vom 24. bis 25. Dezember sowie vom 31. Dezember bis 2. Januar zu sich zu nehmen. Hinsichtlich D._ wurde das Besuchs- und Ferienrecht gegenüber dem Scheidungsurteil nicht geändert, d.h. A._ soll berechtigt bleiben, D._ jeden zweiten Freitag nach der Schule bis Sonntagabend zu sich zu nehmen und die Ferien sollen nach Absprache hälftig geteilt werden. Auch die Feiertage Pfingsten, Ostern, Weihnachten und Silvester sollen im jährlichen Wechsel aufgeteilt werden. Das Obergericht ergänzte diese Regelung durch dieselbe Aufteilung für den Konfliktfall wie bei C._. Das Obergericht verpflichtete A._ schliesslich zur Bezahlung folgender monatlicher Kinderunterhaltsbeiträge bis zum ordentlichen Abschluss einer angemessenen Ausbildung: Für C._ ab 1. Oktober 2010 Fr. 1'000.--, ab 1. Mai 2011 Fr. 1'250.-- und ab 1. August 2011 Fr. 1'400.--; für D._ ab 1. Oktober 2010 Fr. 1'000.-- und ab 1. Februar 2015 Fr. 1'250.--. Im Übrigen wies das Obergericht die Abänderungsklage ab. Für C._ ordnete es eine Beistandschaft gemäss <ref-law> zur Förderung des Kontakts mit ihrem Vater an. Den Antrag auf weitere Kindesschutzmassnahmen wies das Obergericht ab.
D. Am 14. März 2013 hat A._ (Beschwerdeführer) gegen das obergerichtliche Urteil Beschwerde an das Bundesgericht erhoben. Er verlangt, C._ unter der gemeinsamen elterlichen Sorge zu belassen. Ausserdem verlangt er Korrekturen bei der Weihnachtsregelung für beide Kinder und bei der Ferienregelung für C._. Ferner beantragt er, die Klage von B._ (Beschwerdegegnerin) auf Abänderung des Kinderunterhaltsbeitrags abzuweisen oder die Sache zur Neuberechnung an die Vorinstanz zurückzuweisen. Schliesslich ersucht er um aufschiebende Wirkung.
Mit Verfügung vom 15. März 2013 hat das Bundesgericht das Gesuch um aufschiebende Wirkung abgewiesen.
Das Bundesgericht hat die Akten beigezogen, aber keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Das angefochtene Urteil betrifft die Zuteilung der elterlichen Sorge und damit zusammenhängend das Besuchsrecht und den Kindesunterhalt. Folglich geht es um eine Zivilsache (<ref-law>) ohne Vermögenswert (<ref-ruling> E. 2 S. 494 ff.). Die Beschwerde in Zivilsachen ist insoweit grundsätzlich zulässig.
1.2 Mit der Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht grundsätzlich von Amtes wegen an (<ref-law>; vgl. für Ausnahmen Abs. 2 dieser Norm) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es befasst sich aber nur mit formell ausreichend begründeten Rügen (<ref-law>; <ref-ruling> E. 1.1 S. 104 f.). In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Allgemein gehaltene Einwände, die ohne aufgezeigten oder erkennbaren Zusammenhang mit bestimmten Entscheidungsgründen vorgebracht werden, genügen nicht (<ref-ruling> E. 1.3 S. 584 mit Hinweisen).
1.3 Für das Bundesgericht ist der vorinstanzlich festgestellte Sachverhalt grundsätzlich verbindlich (<ref-law>). Seine Feststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig - d.h. willkürlich (<ref-ruling> E. 1.5 S. 130 mit Hinweis) - ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>). Inwiefern diese Voraussetzungen erfüllt sein sollen, muss in der Beschwerde substantiiert begründet werden (<ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 5.1 S. 356). Dabei ist zu beachten, dass bei der Rüge der offensichtlich unrichtigen Sachverhaltsfeststellung das strenge Rügeprinzip (<ref-law>) gilt und demnach anhand der Erwägungen des angefochtenen Entscheids klar und detailliert darzulegen ist, inwiefern die vorinstanzliche Sachverhaltsfeststellung willkürlich sein soll. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten (<ref-ruling> E. 1.4.2 und 1.4.3 S. 254 f.). Auf solche rein appellatorische Kritik am Sachverhalt tritt das Bundesgericht nicht ein (BGE <ref-ruling> E. 5.1 S. 356 mit Hinweis). Neue Tatsachen und Beweismittel dürfen vor Bundesgericht schliesslich nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. Strittig ist zunächst die Zuteilung der elterlichen Sorge.
2.1 Das Obergericht hat die Aufhebung der gemeinsamen elterlichen Sorge für C._ mit der fehlenden Kooperationsfähigkeit der Eltern begründet. So habe die Beschwerdegegnerin einen gerichtlichen Beschluss erwirken müssen, um die Kinder aus der deutschen Grundschule abzumelden und in der Schweiz in der Schule bzw. im Kindergarten anmelden zu können, und dies obwohl die Parteien am 1. Oktober 2007 vereinbart hätten, dass die Beschwerdegegnerin mit den Kindern in die Schweiz umziehen dürfe. Des Weiteren sei es zu Vollstreckungsverfahren für das Besuchsrecht für C._ gekommen. Das Besuchsrecht sei dauernd Gegenstand unterschiedlicher Auffassungen gewesen, insbesondere im Zusammenhang mit der von C._ gewünschten Teilnahme am Ballettunterricht und an Ballettaufführungen. Das Obergericht nennt als Beispiel eine E-Mail des Beschwerdeführers an seine Tochter vom 12. Mai 2010, in der er ihr jegliche Ballettaktivität an Besuchstagen verbietet und sich rechtliche Schritte gegen die Ballettschule vorbehält. Dieser Umgang sei wenig einfühlsam und lasse auf fehlendes Verständnis für die Interessen der Tochter schliessen. Der Beschwerdeführer habe seiner Tochter durch Schuldzuweisungen das Gefühl vermittelt, alleine für die verfahrene Situation verantwortlich zu sein und nicht nur zu seinem, sondern auch zum Nachteil des Rests der Familie (Bruder, Beschwerdegegnerin, Grossmutter) zu handeln. Das Obergericht ist zum Schluss gekommen, die damit verbundenen Belastungen könnten mit der Zuteilung der elterlichen Sorge an die Beschwerdegegnerin eingeschränkt werden. Ähnliches gelte für die Meinungsverschiedenheiten bei der Schulwahl. Obschon C._ bereits vor Amtsgericht Starnberg die Absicht geäussert habe, das Abitur zu machen, habe die Beschwerdegegnerin für ihre Anmeldung an ein öffentliches Gymnasium in F._ ein Massnahmeverfahren anstrengen müssen. Es falle dem Beschwerdeführer offensichtlich schwer, die Wünsche der Tochter zu akzeptieren oder auf diese einzugehen, stattdessen setze er sie einer grossen Belastung aus. Die Umteilung der elterlichen Sorge sei deshalb angezeigt.
Trotz gewisser Bedenken sah das Obergericht zur Zeit keinen Anlass, auch die (bisher gemeinsame) elterliche Sorge für D._ neu zu regeln. Eine Abänderung sei erst bei Gefährdung des Kindeswohls vorzunehmen. D._ sei jedoch keinem besonderen Druck ausgesetzt gewesen, habe ein sehr gutes Verhältnis zu seinem Vater und die blosse Gefahr, dass die Entwicklung wie bei seiner Schwester verlaufen könnte, genüge nicht für eine Umteilung. Aufgrund des Altersunterschieds der Kinder und ihrer unterschiedlichen Kontakte zum Beschwerdeführer dränge es sich auch nicht auf, beide gleich zu behandeln.
2.2 Gemäss <ref-law> ist die Zuteilung der elterlichen Sorge neu zu regeln, wenn dies wegen wesentlicher Veränderung der Verhältnisse zum Wohl des Kindes geboten ist. Nach konstanter Rechtsprechung des Bundesgerichts kommt eine Änderung des Sorgerechts nur in Betracht, wenn die Beibehaltung der geltenden Regelung das Wohl des Kindes ernsthaft zu gefährden droht. Die Veränderung der Verhältnisse muss somit die Änderung der Sorgerechtsregelung zwingend gebieten, weil die aktuelle Regelung dem Kind mehr schadet als eine Änderung derselben und der damit verbundene Verlust an Kontinuität in der Erziehung und den Lebensumständen (Urteile 5C.63/2005 vom 1. Juni 2005 E. 2, nicht publ. in: <ref-ruling>; 5A_616/2007 vom 23. April 2008 E. 7.1; 5A_483/2011 vom 31. Oktober 2011 E. 3.2, in: FamPra.ch 2012 S. 206; 5A_105/2012 vom 9. März 2012 E. 2.3; je mit Hinweisen). Insbesondere im Falle gemeinsamer elterlicher Sorge ist eine Änderung nur gerechtfertigt, wenn die Grundbedingungen für eine gemeinsame Verantwortung der Eltern nicht mehr gegeben sind, so dass das Kindeswohl die Übertragung der elterlichen Sorge an einen Elternteil gebietet. Dies trifft unter anderem zu, wenn Kooperationswille und Kooperationsfähigkeit der Eltern nicht mehr bestehen (Urteile 5A_616/2007 vom 23. April 2008 E. 7.1; 5A_170/2009 vom 10. Juni 2009 E. 3.1; 5A_645/2008 vom 27. August 2009 E. 4.1, in: FamPra.ch 2009 S. 1076 und Pra 2010 Nr. 71 S. 515; je mit Hinweisen).
Ob eine wesentliche Veränderung im dargelegten Sinn vorliegt, ist aufgrund sämtlicher Umstände des konkreten Einzelfalles zu beurteilen. Bei der Beurteilung steht den kantonalen Behörden, welche die Parteien und die Verhältnisse besser kennen als das Bundesgericht, ein erhebliches Ermessen zu. Das Bundesgericht greift nur ein, wenn einschlägige Kriterien grundlos ausser Betracht geblieben oder offenkundig falsch gewichtet worden sind, oder wenn die Zuteilung auf Überlegungen abgestützt worden ist, die unter dem Gesichtswinkel des Kindeswohls bedeutungslos sind oder gegen die dargelegten bundesgerichtlichen Grundsätze verstossen. Diese Kognitionsbeschränkung gilt auch mit Bezug auf die Aufhebung der gemeinsamen elterlichen Sorge (Urteil 5A_170/2009 vom 10. Juni 2009 E. 3.1 mit Hinweisen).
2.3 Der Beschwerdeführer hält die Voraussetzungen für die Umteilung der elterlichen Sorge nicht für gegeben.
Er macht zunächst geltend, es sei nicht festgestellt worden, dass die Diskussion um die Schulwahl C._ tatsächlich belastet habe. Damit setzt er sich über die gegenteilige obergerichtliche, für das Bundesgericht grundsätzlich verbindliche Feststellung hinweg, ohne darzulegen, inwieweit diese willkürlich sein soll. Er macht ausserdem geltend, das Obergericht habe keine genauen Feststellungen darüber getroffen, wie die Eltern in dieser Frage - nach Einleitung eines Massnahmeverfahrens - doch noch zu einer Einigung gelangt sind. Über seine entsprechenden Behauptungen im erstinstanzlichen Verfahren sei kein Beweis geführt worden. Abgesehen davon, dass er nicht belegt, Entsprechendes vor Bezirksgericht überhaupt behauptet zu haben, hätte er die Rüge bereits vor Obergericht vorbringen müssen. Dass er dies getan hätte, macht er nicht geltend.
Der Beschwerdeführer behauptet weiter, dass C._ das Ballett nicht mehr intensiv betreibe, so dass sich auch der Konflikt um das Besuchsrecht entschärft habe. Das Verhältnis habe sich seit mehreren Monaten namhaft verbessert, weshalb sie auch wieder mit Übernachtungen bei ihm einverstanden sei. Aus dem angefochtenen Urteil ergibt sich jedoch nicht, dass sich ihr Verhältnis seit mehreren Monaten namhaft verbessert habe oder dass C._ Ballett nicht mehr intensiv betreibe. Diese Tatsachenbehauptungen sind entweder neu und deshalb unzulässig (<ref-law>) oder dann legt der Beschwerdeführer nicht dar, inwieweit das Obergericht rechtzeitig ins kantonale Verfahren eingeführte Behauptungen übergangen und dieses damit den Sachverhalt willkürlich festgestellt haben soll. Darauf ist nicht einzutreten. Hingegen trifft zu, dass C._ mit Übernachtungen bei ihrem Vater wieder einverstanden ist (vgl. unten E. 3.1). Dies betrifft jedoch nicht die Frage, ob die Eltern kooperationsfähig sind und ob der Beschwerdeführer im Rahmen der gemeinsamen elterlichen Sorge in der Lage ist, im gebotenen Masse auch die Wünsche der Tochter zu berücksichtigen. Es hat höchstens Einfluss darauf, in welchem Masse das Besuchsrecht weiterhin Anlass zu Streit bilden könnte.
Er rügt ausserdem, es sei unberücksichtigt geblieben, dass C._ keine Veränderung der Sorgerechtszuteilung wünsche. Wann sie diesen Wunsch im Laufe des Verfahrens geäussert haben soll, erläutert er nicht. Ihre angebliche, nochmalige entsprechende Bestätigung in einem Gespräch am 8. März 2013 stammt jedenfalls aus der Zeit nach Erlass des angefochtenen Urteils, ist somit neu und deshalb unbeachtlich (vgl. <ref-ruling> E. 2.1 S. 343 f.).
Der Beschwerdeführer macht ferner geltend, das Obergericht habe keine veränderten Verhältnisse festgestellt. Seit dem Urteil des Amtsgerichts Starnberg hätten sich die Verhältnisse nicht negativ verändert, sondern es sei im Gegenteil eine Beruhigung festzustellen. Zudem stünden keine dringlichen Sorgerechtsfragen an, so dass keine aktuelle Gefährdung des Kindeswohls vorliege. Auch insoweit handelt es sich weitgehend um Tatsachenbehauptungen (angebliche Beruhigung der Verhältnisse, Nichtbevorstehen von Sorgerechtsfragen), wobei diese entweder neu sind oder dann zumindest nicht dargelegt wird, inwieweit die Vorinstanz den Sachverhalt in dieser Hinsicht willkürlich festgestellt haben soll. Der Beschwerdeführer übergeht im Übrigen, dass die Vorinstanz die massgebliche Veränderung im Wegfall der Kooperationsfähigkeit der Parteien gesehen hat. Entgegen dem Bezirksgericht hat das Obergericht dabei ausdrücklich nicht darauf abgestellt, dass das Verhältnis bereits in der Trennungszeit, d.h. vor dem Scheidungsurteil, schlecht gewesen sei, sondern es hat sich auf Umstände gestützt, die nach der Scheidung eingetreten sind. Rein appellatorisch sind schliesslich die Ausführungen des Beschwerdeführers, dass das Obergericht ihm einseitig die Schuld zugeschoben habe und dass im Gegenteil die Eskalationen stets durch die Beschwerdegegnerin erfolgt seien und sie das gemeinsame Sorgerecht sabotiert habe.
3. Umstritten ist des Weiteren das Besuchs- und Ferienrecht.
3.1 Nach der Vereinbarung der Parteien vom 1. Oktober 2007 hatte A._ das Recht, die Kinder jeden zweiten Freitag nach der Schule bis Sonntag, 20.00 Uhr (abzüglich der Transportzeiten, wenn B._ die Kinder bringt und holt), zu sich zu nehmen. Die Ferien sollten hälftig zwischen den Eltern gemäss vorheriger Absprache aufgeteilt und die Feiertage Pfingsten, Ostern, Weihnachten und Silvester im jährlichen Wechsel aufgeteilt werden. Schliesslich sollte der zeitliche und finanzielle Aufwand zwischen den Eltern hälftig geteilt werden und sich insbesondere beide bemühen, die Fahrten hälftig zu übernehmen.
Das Obergericht hat erwogen, wenn die Eltern nicht in der Lage seien, in Absprache mit den Kindern eine einst getroffene Besuchsrechtsregelung neuen Verhältnissen anzupassen, so sei diese durch das Gericht in erster Linie im Lichte des Kindeswohls und nicht nach den Wünschen der Eltern anzupassen.
Bezüglich C._ hat das Obergericht die Beziehung zwischen ihr und ihrem Vater als tragfähig beurteilt. C._ möchte regelmässige Kontakte und sei auch damit einverstanden, beim Vater zu übernachten. Angesichts ihrer übrigen Aktivitäten (insbesondere Lernen am Sonntag und Kontakte mit Freundinnen am Samstag) möchte sie diese jedoch auf ein Mal pro Monat einschränken. Der Beschwerdeführer hingegen habe seine Tochter durch seine Forderungen, entweder das ganze Wochenende bei ihm zu verbringen oder gar nicht, unter Druck gesetzt. Die Vorstellungen von C._ seien angesichts der Streitigkeiten um das Besuchsrecht, der Schulsituation und ihrer weiteren Bedürfnisse nachvollziehbar. Ihre Wünsche und Bedürfnisse als bald 14-jährige Gymnasiastin seien in die Entscheidfindung einzubeziehen und das Besuchsrecht entsprechend auszugestalten. Das Obergericht hat ihr Besuchsrecht demgemäss auf jedes vierte Wochenende vom Samstag, 9.30 Uhr, bis Sonntag, 19.00 Uhr, angesetzt. Mit einem minimalen Ferienbesuchsrecht sei sie einverstanden, wobei weitere Ferien besprochen werden könnten. Demgemäss sei ein Ferienrecht von einer Woche während der Sommerferien festzusetzen, wobei weitere Ferienbesuchsrechte nach Absprache der Parteien mit C._ vereinbart werden könnten. Hinsichtlich der Feiertagsregelung hat das Obergericht keinen Anlass gesehen, von der bisherigen Regel abzuweichen, wonach die Feiertage Pfingsten, Ostern, Weihnachten und Silvester im jährlichen Wechsel aufzuteilen seien. Einzig die Ersatzregelung für den Fall, dass sich die Parteien nicht einigen könnten, sei gegenüber dem bezirksgerichtlichen Urteil abzuändern, nachdem der Beschwerdeführer kritisiert habe, dass das Bezirksgericht hier für Weihnachten und Silvester ohne Parteiantrag eine Änderung vorgenommen habe. Für den Fall, dass sich die Parteien nicht einigen könnten, sei deshalb - wie üblich - festzuschreiben, dass die Weihnachtstage aufgeteilt würden und das Besuchsrecht am Jahresende alterniere. Die Feiertagsregelung sei für C._ und D._ gleich zu gestalten. Der Transport sei wie bis anhin unter den Eltern aufzuteilen.
3.2 Der Beschwerdeführer wendet sich gegen die Feiertagsregelung für Weihnachten und Silvester (für beide Kinder) sowie gegen die Ferienregelung (für C._). Sein Antrag, die Regelungen "aufzuheben bzw. zu korrigieren" ist jedoch unbestimmt, wenigstens was den reformatorischen Teil desselben betrifft. Bei der Feiertagsregelung lässt sich der Beschwerdebegründung immerhin entnehmen, dass die Kinder die gesamten Weihnachtstage jährlich abwechselnd bei einem Elternteil und Silvester/Neujahr beim andern Elternteil verbringen sollen. Ob der Beschwerdeführer diesbezüglich eine Regelung nur für eigentlichen Feiertage wünscht oder sogar für die ganzen Winterferien, wird jedoch nicht restlos klar, führt er doch auch aus, dass die Kinder bisher jährlich abwechselnd die erste Ferienhälfte beim einen Elternteil und die zweite beim andern Elternteil verbrachten. So oder anders macht er geltend, die Vorinstanz habe die Parteien zu dieser Regelung nicht angehört und sie sei so auch von niemandem gewünscht worden. Diesbezüglich ist vorauszuschicken, dass die kritisierte Regelung einzig für den Konfliktfall gilt. Es steht den Parteien demnach frei, die Festtage weiterhin in der Art aufzuteilen, wie sie nach der Behauptung des Beschwerdeführers bis anhin aufgeteilt worden sind. Inwieweit die Parteien zur Ersatzregelung nicht angehört worden seien, konkretisiert der Beschwerdeführer nicht weiter. Insbesondere übergeht er, dass er für die Ersatzregelung nach der obergerichtlichen Feststellung keine konkreten Vorschläge gemacht hat, obschon eine solche im Verfahren thematisiert worden ist, und er die bezirksgerichtliche Ersatzregelung selber angefochten hatte. Wenn er schliesslich die vier Übergabetermine über Weihnachten und Neujahr als nicht praktikabel beurteilt, so geht er damit einzig von seiner Sicht der Dinge aus. Abgesehen davon finden seine Behauptungen über das übliche Programm in den Winterferien (Ferien in G._ und anderswo) keine Stütze im angefochtenen Urteil.
Entsprechendes gilt auch für seinen Einwand der fehlenden Praktikabilität der Sommerferienregelung für C._. Im Übrigen lässt sich hier nicht einmal der Begründung der Beschwerde entnehmen, welche Regelung er vorziehen würde. Es ist schliesslich daran zu erinnern, dass nach Absprache eine Verlängerung des Ferienrechts für C._ in Betracht kommt, so dass auch längere Auslandsferien mit dem Beschwerdeführer nicht verunmöglicht werden.
4. Umstritten sind schliesslich die Kinderunterhaltsbeiträge für beide Kinder.
4.1 In der dem Scheidungsurteil zugrunde liegenden Vereinbarung einigten sich die Parteien dahin gehend, dass es bei der bestehenden Kindesunterhaltsregelung bleiben solle und der Kindesunterhalt deutschem Recht unterliege. Damit verwiesen sie auf das Urteil des Oberlandesgerichts München vom 13. Juni 2005. Für C._ war darin ein Unterhaltsbeitrag von 200 % des Regelbetrags der Regelbetragsverordnung, abgestuft nach Alter, abzüglich des anrechenbaren Kindergeldes vorgesehen, d.h. bis 30. April 2005 gemäss Altersstufe 1, vom 1. Mai 2005 bis 30. April 2011 gemäss Altersstufe 2 der dann geltenden Düsseldorfer Tabelle, und ab 1. Mai 2011 gemäss Altersstufe 3 der dann geltenden Düsseldorfer Tabelle. Hinzu kommen über den gesamten Zeitraum monatlich EUR 81.--. Für D._ sollte eine analoge Regelung gelten mit folgenden Abstufungen: bis 31. Januar 2009 gemäss Altersstufe 1, vom 1. Februar 2009 bis 31. Januar 2015 gemäss Altersstufe 2 der dann geltenden Düsseldorfer Tabelle und ab 1. Februar 2015 gemäss Altersstufe 3 der dann geltenden Düsseldorfer Tabelle. Auch bei ihm sollten monatlich EUR 81.-- über den ganzen Zeitraum hinzukommen. Gemäss der obergerichtlichen Feststellung bedeutet dies, dass sich die Unterhaltsbeiträge für beide Kinder auf je EUR 554.-- bzw. für C._ ab 1. Mai 2011 auf EUR 647.-- belaufen, je zuzüglich EUR 81.-- Krankenkassenkosten, d.h. auf total EUR 635.-- und EUR 728.--.
Das Obergericht hat zunächst die Rechtswahlklausel als unzulässig beurteilt und auf die Unterhaltsabänderung Schweizer Recht angewandt. Sie sah im Umzug in die Schweiz keinen Abänderungsgrund, da dieser bereits in der Vereinbarung vom 1. Oktober 2007 vorgesehen war. Auch die Umteilung der elterlichen Sorge über C._ sei kein Abänderungsgrund, denn damit sei keine wesentliche Änderung in der Betreuung verbunden, dies auch nicht unter Berücksichtigung der reduzierten Besuche beim Beschwerdeführer. Hingegen habe der Euro seit der Scheidung mehr als 20 % an Wert verloren. Angesichts der Dauer dieser Entwicklung sei von einer erheblichen und unvorhersehbaren Änderung auszugehen und eine entsprechende Anpassung vorzunehmen. Auch der Beschwerdeführer anerkenne, dass es für die Parteien klar gewesen sei, dass der Kindesunterhalt in Franken und nicht in Euro bestritten werden müsse. Der Unterhaltsbeitrag sei neu in Franken festzusetzen, denn einerseits sei die der Vereinbarung zugrunde liegende Regelbetragsverordnung inzwischen aufgehoben worden und der Beschwerdeführer erziele sein Einkommen auch in Franken. Bei einem Umrechnungskurs im Scheidungszeitpunkt von Fr. 1.58 ergäben sich Unterhaltsbeiträge Fr. 1'003.30 bzw. Fr. 1'150.25. Beim heutigen Kurs von Fr. 1.25 ergäben sich bloss Fr. 793.75 bzw. Fr. 910.--, womit die Änderung augenfällig sei. Die Unterhaltsbeiträge seien deshalb in einem ersten Schritt neu auf gerundet Fr. 1'000.-- bzw. Fr. 1'150.-- festzusetzen zuzüglich allfälliger Kinderzulagen und diese Anpassung gelte ab Klageeinleitung (1. Oktober 2010). Ab August 2011 seien die Unterhaltsbeiträge für C._ zur Deckung der Mehrkosten durch den Besuch des Gymnasiums zudem um Fr. 250.-- zu erhöhen. Diese Kosten seien in der altersmässigen Abstufung der Düsseldorfer Tabellen und den daraus folgenden Erhöhungen des Unterhaltsbeitrags nicht abgedeckt.
4.2 Der Beschwerdeführer wendet sich nicht gegen die Anwendung von Schweizer Recht auf die Anpassung der Kinderunterhaltsbeiträge. Somit richten sich die Voraussetzungen für die Abänderung von Kinderunterhaltsbeiträgen, die in einem Scheidungsurteil festgesetzt wurden, nach den Bestimmungen über die Wirkungen des Kindesverhältnisses (<ref-law>), d.h. nach <ref-law>. Eine Neufestsetzung gemäss <ref-law> setzt voraus, dass sich der relevante Sachverhalt nachträglich erheblich und dauerhaft verändert hat. Eine Abänderungsklage bezweckt nicht die Korrektur eines fehlerhaften rechtskräftigen Urteils, sondern die Anpassung eines rechtskräftigen Urteils - ob fehlerhaft oder nicht - an veränderte Verhältnisse (<ref-ruling> E. 4.1.1 S. 606; Urteil 5A_506/2011 vom 4. Januar 2012 E. 3.1, in: FamPra.ch 2012 S. 486). Soweit die Veränderungen im Scheidungsurteil bereits berücksichtigt sind (vgl. <ref-law>), kommt keine Anpassung in Betracht (<ref-ruling> E. 5b S. 310 f.; <ref-ruling> E. 2.7.4 S. 199).
Liegt eine erhebliche und dauerhafte nachträgliche Sachverhaltsänderung vor, führt dies nicht automatisch zu einer Neufestsetzung des Unterhaltsbeitrags. Es kommt nur dann zu einer Neufestsetzung, wenn ansonsten mit Blick auf das ursprüngliche Scheidungsurteil ein unzumutbares Ungleichgewicht zwischen den involvierten Personen entstehen könnte. Zur Beurteilung dieser Voraussetzung gilt es die Interessen von Vater, Mutter und Kind bzw. Kindern gegeneinander abzuwägen (<ref-ruling> E. 4.1.1 S. 606; Urteil 5A_506/2011 vom 4. Januar 2012 E. 4.1, in: FamPra.ch 2012 S. 486).
Liegt eine erhebliche und dauerhafte nachträgliche Sachverhaltsänderung vor, führt dies nicht automatisch zu einer Neufestsetzung des Unterhaltsbeitrags. Es kommt nur dann zu einer Neufestsetzung, wenn ansonsten mit Blick auf das ursprüngliche Scheidungsurteil ein unzumutbares Ungleichgewicht zwischen den involvierten Personen entstehen könnte. Zur Beurteilung dieser Voraussetzung gilt es die Interessen von Vater, Mutter und Kind bzw. Kindern gegeneinander abzuwägen (<ref-ruling> E. 4.1.1 S. 606; Urteil 5A_506/2011 vom 4. Januar 2012 E. 4.1, in: FamPra.ch 2012 S. 486).
4.3 4.3.1 Der Beschwerdeführer rügt zunächst eine Verletzung des rechtlichen Gehörs. Das Obergericht habe ihn zur Neuberechnung nicht angehört, obwohl er beantragt habe, die Berechnung sei zur Feststellung des Sachverhalts an das Bezirksgericht zurückzuweisen. Er habe nicht damit rechnen können, dass das Obergericht bloss einzelne Teile der Argumentation der Beschwerdegegnerin übernehme und gestützt darauf selber eine Berechnung vornehmen werde, ohne ihm Gelegenheit zu geben, zum Thema des Wechselkurses und der Beträge gemäss Düsseldorfer Tabelle Stellung zu nehmen.
Diese Rüge geht fehlt. Dass der Beschwerdeführer nicht insgesamt zu den Eingaben der Beschwerdegegnerin hätte Stellung nehmen können, behauptet er selber nicht. Es ist nicht ersichtlich, weshalb er seine Einwände gegen ihre Argumentation oder Teile derselben nicht vor Obergericht hätte vortragen können, zumal immer damit gerechnet werden muss, dass ein Gericht sich nur Teile der gegnerischen Parteistandpunkte zu eigen machen wird. Es mag zwar zutreffen, dass er in der Berufung eine Rückweisung zur Neuberechnung beantragt hat. Die Berufung ist jedoch ein reformatorisches Rechtsmittel, bei der die Parteien mit einem neuen Sachentscheid rechnen müssen (<ref-law> [SR 272]). Das Obergericht hat denn auch dargelegt, dass es den Sachverhalt für liquide hält und es die Neuberechnung folglich selber vornimmt.
4.3.2 Im Übrigen kritisiert er die Berechnung der Unterhaltsbeiträge und die Bestimmung des Wechselkurses. Er begnügt sich jedoch im Wesentlichen damit, die Aktenwidrigkeit der Berechnung durch die Vorinstanz zu behaupten, indem er der obergerichtlichen Berechnung verschiedene eigene Berechnungen für verschiedene Zeitpunkte gegenüberstellt, wobei er insbesondere andere Umrechnungskurse benutzt. Eine konkrete Auseinandersetzung mit den vom Obergericht herangezogenen Zahlen und Berechnungsergebnissen (gemäss Erwägungen und Dispositiv) fehlt. Darauf ist nicht einzutreten. Ausserdem will er die Wechselkursentwicklung durch die Inflation kompensieren, die in Deutschland im fraglichen Zeitraum angeblich deutlich höher gewesen sein soll als in der Schweiz. Die Verluste beim Kindesunterhalt betrügen damit maximal 13 %, was keine wesentliche Änderung darstelle. Die Frage, welche Inflationsrate in welchem Zeitraum in verschiedenen Ländern herrschte (und inwieweit diese sich in einem Regelwerk wie den Düsseldorfer Tabellen, auf die sich der Beschwerdeführer beruft, niederschlugen), betrifft den Sachverhalt. Die entsprechenden Behauptungen sind entweder neu und deshalb unzulässig (<ref-law>) oder dann legt der Beschwerdeführer zumindest nicht dar, inwieweit er entsprechende Behauptungen rechtzeitig ins kantonale Verfahren eingeführt hat und die Vorinstanz diese in willkürlicher Weise übergangen haben soll (<ref-law>). Der Beschwerdeführer behauptet weiter, dass die Kinderzulagen nach dem deutschen Scheidungsurteil den Eltern hälftig zustehen sollen und nicht von ihm vollständig zusätzlich geschuldet seien. Die Behauptung ist unsubstantiiert, nennt er doch keine Stelle des Scheidungsurteils, aus der sich dies ergeben soll.
5. Die Beschwerde ist somit abzuweisen, soweit auf sie eingetreten werden kann.
6. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 30. April 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Zingg