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 Art. 308 Abs. 2 ZGB 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 Art. 308 Abs. 2 ZGB 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.