Sachverhalt: A. A.a. A._ (geb. 1981, Staatsangehörige des Kosovo) und B._ (geb. 1952) heirateten 2004 in Kosovo, worauf die Ehefrau in die Schweiz einreiste und eine Aufenthaltsbewilligung erhielt. Am 17. August 2009 erteilte ihr das Migrationsamt die Niederlassungsbewilligung. Am 15. Oktober 2009 leitete B._ im Kosovo die Scheidung ein. Mit Urteil des Amtsgerichts Peja/Kosovo vom 2. Februar 2010 wurde die (kinderlose) Ehe geschieden. A.b. A._ hielt sich ab dem Jahr 2000 bereits einige Zeit als Asylbewerberin in der Schweiz auf. B._ ist Vater von vier Kindern aus einer früheren Ehe. B. B.a. Am 18. September 2010 wurde A._ Mutter eines Sohnes, den B._ am 20. Oktober 2010 (A._ und B._ sprechen vom 20. Oktober 2012) anerkannte. Ein DNA-Test liegt nicht vor. B.b. Mit Verfügung vom 8. August 2011 widerrief das Migrationsamt die Niederlassungsbewilligung von A._ mit der Begründung, die beiden hätten eine Scheinehe gelebt. Die Sicherheitsdirektion sowie das Verwaltungsgericht Zürich bestätigten auf Rechtsmittel hin den abschlägigen Rechtsspruch (Entscheide vom 6. Juli 2012 und 20. Februar 2013). C. C.a. Am 22. August 2012 ersuchten A._ und B._ das Zivilstandsamt Winterthur um Durchführung des Vorbereitungsverfahrens für eine erneute Eheschliessung. Das Zivilstandsamt vermutete einen Zusammenhang mit dem ausländerrechtlichen Verfahren. Es hörte A._ und B._ am 4. September 2012 getrennt an und lud sie zu einer ergänzenden Stellungnahme. Am 2. Oktober 2012 fand ein weiteres Gespräch statt. C.b. Mit Verfügung vom 16. November 2012 verweigerte das Zivilstandsamt die Mitwirkung am Eheschliessungsverfahren. C.c. Die hiergegen erhobenen Beschwerden wiesen die Direktion der Justiz und des Innern des Kantons Zürich mit Verfügung vom 29. August 2013 und in der Folge auch das Verwaltungsgericht des Kantons Zürich mit Urteil vom 20. November 2013 ab. D. A._ und B._ (Beschwerdeführer) gelangen gegen den Entscheid des Verwaltungsgerichts mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 14. Januar 2014 an das Bundesgeric ht. Sie beantragen, das Urteil des Verwaltungsgerichts sei aufzuheben und das Zivilstandsamt Winterthur sei anzuweisen, ihnen die Eheschliessung zu bewilligen. Die Kosten und Entschädigungen seien dem Zivilstandsamt aufzuerlegen. Das Bundesgericht hat die Akten, in der Sache aber keine Vernehmlassungen eingeholt. E. Auch gegen den Widerruf der Niederlassungsbewilligung gelangte A._ an das Bundesgericht. Die II. öffentlich-rechtliche Abteilung hiess ihre Beschwerde mit Urteil 2C_303/2013 vom 13. März 2014 gu t.