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.

Erwägungen:
1.
1.1. Das Bundesgericht überprüft von Amtes wegen und mit freier Kognition, ob eine Beschwerde zulässig ist (<ref-ruling> E. 1 S. 216; <ref-ruling> E. 1 S. 117; je mit Hinweisen).
1.2. Die Beschwerdeführer bezeichneten ihr Rechtsmittel an das Bundesgericht als Beschwerde in öffentlich-rechtlichen Angelegenheiten. Angefochten ist ein Entscheid des Verwaltungsgerichts Zürich, der die Weigerung des Zivilstandsamts Winterthur, am Eheschliessungsverfahren der Beschwerdeführer mitzuwirken (<ref-law>), bestätigt. Es handelt sich um eine öffentlich-rechtliche Angelegenheit in unmittelbarem Zusammenhang mit dem Zivilrecht (Art. 72 Abs. 2 lit. b Ziff. 2 BGG; Urteile 5A_225/2011 vom 9. August 2011 E. 1. 1; 5A_753/2009 vom 18. Januar 2010 E. 1.1). Anwendbar sind demnach die Bestimmungen über die Beschwerde in Zivilsachen nach <ref-law>, wie dies die Vorinstanz in der Rechtsmittelbelehrung des angefochtenen Entscheids korrekt vorgezeichnet hat.
1.3. Der angefochtene Endentscheid erging auf Rechtsmittel hin und ist kantonal letztinstanzlich (Art. 75 Abs. 1, Art. 90 BGG). Die Beschwerdeführer sind gemäss <ref-law> zur Beschwerde berechtigt und die Frist ist eingehalten (<ref-law>). Insofern sind die Voraussetzungen der Beschwerde in Zivilsachen erfüllt und die eingereichte Beschwerde ist unbeachtlich der falschen Bezeichnung als solche entgegenzunehmen (<ref-ruling> E. 1.2 S. 382; Urteil 5A_753/2009 vom 18. Januar 2010 E. 1.1).
2.
2.1. Im ordentlichen Beschwerdeverfahren sind vor Bundesgericht in rechtlicher Hinsicht alle Rügen gemäss Art. 95 f. BGG zulässig. Unter Vorbehalt des Bereichs der verfassungsmässigen Rechte - und weiterer vorliegend nicht gegebener Ausnahmen (<ref-law>) - wendet das Bundesgericht das Recht von Amtes wegen an (<ref-law>; <ref-ruling> E. 4 S. 252 mit Hinweis). Es kann die Beschwerde daher auch aus andern als den geltend gemachten Gründen gutheissen oder den Entscheid mit einer Begründung bestätigen, die von jener der Vorinstanz abweicht (zu den Voraussetzungen der Motivsubstitution <ref-ruling> E. 4 S. 252 mit Hinweis).
2.2. Dagegen ist das Bundesgericht an den festgestellten Sachverhalt grundsätzlich gebunden (<ref-law>). Gegen die tatsächlichen Feststellungen der Vorinstanz kann der Beschwerdeführer einzig vorbringen, sie seien offensichtlich unrichtig (<ref-law>), das heisst willkürlich (<ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398), oder sie würden auf einer anderen Rechtsverletzung im Sinne von <ref-law> (z. B. <ref-law> oder <ref-law>) beruhen. Ausserdem muss er in der Beschwerde aufzeigen, inwiefern die Behebung der vorerwähnten Mängel für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2 S. 22). Für all diese Elemente gilt das strenge Rügeprinzip (<ref-law>; <ref-ruling> E. 1.4.3 S. 255). Auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 1.2 S. 234; <ref-ruling> E. 3.2 S. 88). Will der Beschwerdeführer die Verletzung des Willkürverbots geltend machen, reicht es sodann nicht aus, wenn er den Sachverhalt aus seiner eigenen Sicht darlegt und die davon abweichenden Feststellungen im angefochtenen Entscheid als willkürlich bezeichnet. Vielmehr muss er neben der Erheblichkeit der gerügten Tatsachenfeststellung im Einzelnen darlegen, inwiefern das kantonale Gericht willkürlich entschieden haben soll und der angefochtene Entscheid deshalb an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246).
3.
3.1. Das Verwaltungsgericht stellte im Wesentlichen auf die Sachverhaltsfeststellungen des Zivilstandsamts Winterthur ab. Dieses hielt zum zeitlichen Ablauf fest, der Beschwerdeführer habe lediglich zwei Monate, nachdem der Beschwerdeführerin die Niederlassungsbewilligung erteilt worden war, die Scheidung eingeleitet. Nur rund anderthalb Monate nach der Abweisung des Rekurses gegen den Widerruf der Niederlassungsbewilligung hätten die Beschwerdeführer um erneute Durchführung des Ehevorbereitungsverfahrens ersucht. Bereits dieser Ablauf stelle ein gewichtiges Indiz dar, dass mit dem anbegehrten Eheschluss ausländerrechtliche Bestimmungen umgangen werden sollten. Anlässlich der getrennten Anhörung vom 4. September 2012 habe die Beschwerdeführerin nicht mit Sicherheit sagen können, wie viele Kinder aus erster Ehe der Beschwerdeführer habe. Sie habe sich nicht an deren Namen erinnern können. Dies obwohl er gemäss eigenen Aussagen in einem guten Kontakt zu seinen Kindern stehe. Auch habe die Beschwerdeführerin nicht gewusst, welcher Arbeit der Beschwerdeführer nachgehe. Er wiederum habe gesagt, die Beschwerdeführerin arbeite wegen des Kindes nicht, während diese erklärt habe, in einem 50 %-Pensum im Geschäft ihrer Brüder, welche in der Schweiz leben, tätig zu sein. Die Vorinstanz befand die gegenseitige Unkenntnis der Arbeitstätigkeit des Anderen ebenso für nicht nachvollziehbar, wie dass die Beschwerdeführerin keinen Namen eines Kindes des Beschwerdeführers nennen konnte. Dass die Beschwerdeführer gegenseitig von wichtigen Personen, Ereignissen und Lebensumständen keine Kenntnis hätten, sei um so weniger verständlich, als eine Verständigung in sprachlicher Hinsicht nicht ausgeschlossen sei; sie könne sich auf Deutsch verständigen und er verstehe etwas Albanisch. Zwischen den Beschwerdeführern bestehe ein Altersunterschied von 29 Jahren. Er sei Sozialhilfebezüger und gehöre damit zu einer typischen Zielgruppe für eine Scheinehe. In Bezug auf das Kind stellte die Vorinstanz fest, zum Zeitpunkt der Einleitung der Scheidung sei die Beschwerdeführerin noch nicht schwanger gewesen. Im Scheidungsurteil vom 2. Februar 2010 sei ausdrücklich festgehalten worden, dass die Ehegatten weder "gemeinsame Kinder hätten noch ein gemeinsames Kind erwarten". Gemäss der polizeilichen Befragung vom 23./28. April 2010 habe ein Kinderwunsch nur seitens der Beschwerdeführerin bestanden; im Laufe dieser Anhörung habe sie die bestehende Schwangerschaft nicht erwähnt. Sowohl von der Direktion der Justiz und des Innern (im eherechtlichen Verfahren) als auch vom Migrationsamt (im ausländerrechtlichen Verfahren) sei der Beschwerdeführer ersucht worden, mittels DNA-Gutachten nachzuweisen, dass er der leibliche Vater sei, was dieser aber verweigere. Zwar brächten die Beschwerdeführer vor, sie lebten zusammen und der Beschwerdeführer übernehme alle Aufgaben eines Vaters; das Kind sage ihm Papi. Angesichts der gesamten Umstände und der Weigerung, die Vaterschaft abklären zu lassen, sei aber anzunehmen, der Beschwerdeführer sei nicht der leibliche Vater. Zusammengefasst führe die Indizienlage zum Schluss, dass der anbegehrte Eheschluss ehefremden Zwecken, nämlich der Umgehung der ausländerrechtlichen Bestimmungen, dienen solle.
Die Vorinstanz erwähnte sodann weitere Abklärungen, welche die Direktion der Justiz und des Innern von der Schweizerischen Botschaft in Kosovo hatte vornehmen lassen. Sie stützte ihren Entscheid aber nicht hierauf ab, weshalb nicht weiter darauf einzugehen ist.
3.2. Die Beschwerdeführer rügen, die Vorinstanz habe Art. 97a und 159 ZGB, <ref-law> sowie Art. 8 und 12 EMRK verletzt und Beweismittel ignoriert oder willkürlich gewürdigt. Diese gehe zu Unrecht davon aus, dass sie keine eheliche Gemeinschaft begründen wollten. Sie würden seit Juli 2010 (wieder) wie ein Ehepaar an der Buchthalerstrasse 149 in Schaffhausen und an der Albrechtstrasse 13 in Winterthur zusammenleben und sich gemeinsam um das Kind kümmern. Die Vorinstanz verfüge nicht über direkte Beweise und die von ihr herangezogenen Indizien stimmten allesamt nicht. Damit habe die Vorinstanz auch den Grundsatz verletzt, dass die Behörde die Beweislast für eine Scheinehe trage. Die blosse Möglichkeit, dass eine Umgehung der ausländerrechtlichen Vorschriften vorliegen könnte, genüge nicht. Auf die Ausführungen der Beschwerdeführer zu den einzelnen Indizien wird nachfolgend (E. 3.4) eingegangen.
Soweit die Beschwerdeführer darüber hinaus eine Verletzung von Verfahrensvorschriften im Zusammenhang mit den Abklärungen durch die Schweizerische Botschaft in Kosovo geltend machen, ist darauf zum vornherein nicht einzutreten, zumal der angefochtene Entscheid ohne Verwendung dieser Abklärungsergebnisse erging (E. 3.1 in fine).
3.3. Gemäss <ref-law> tritt der Zivilstandsbeamte auf ein Eheschliessungsgesuch nicht ein, wenn die Braut oder der Bräutigam offensichtlich keine Lebensgemeinschaft begründen, sondern die Bestimmungen über Zulassung und Aufenthalt von Ausländerinnen und Ausländern umgehen will. Es handelt sich um eine Konkretisierung des Rechtsmissbrauchsverbots gemäss <ref-law>. Der Zivilstandsbeamte darf seine Mitwirkung nur verweigern, wenn die zwei folgenden kumulativen Voraussetzungen erfüllt sind. Erstens muss den Gesuchstellern jeglicher Wille fehlen, eine eheliche Gemeinschaft zu begründen, wobei unter ehelicher Gemeinschaft eine dauerhafte Lebensgemeinschaft grundsätzlich ausschliesslichen Charakters mit einer sowohl geistigen, körperlichen und wirtschaftlichen Komponente verstanden wird. Zweitens müssen sie beabsichtigen, mit der Heirat die Bestimmungen über die Zulassung und den Aufenthalt von Ausländern zu umgehen. Beide Voraussetzungen müssen offenkundig erfüllt sein. Der Wille, eine eheliche Gemeinschaft begründen zu wollen, ist ein intimes Element, welches naturgemäss keinem direkten Beweis zugänglich ist. Ein Missbrauch kann nur durch ein Zusammenspiel von Indizien nachgewiesen werden (vgl. zum Ganzen Urteil 5A_225/2011 vom 9. August 2011 E. 5.1.1, in: FamPra.ch 2011 922, mit einer Zusammenfassung der Lehre und Rechtsprechung; sowie analog bezüglich Scheinehe <ref-ruling> E. 10.2 f. S. 135 f.; <ref-ruling> E. 2.1 f. S. 151 mit Hinweisen).
Solche Indizien können äussere Gegebenheiten sein wie ein grosser Altersunterschied, Schwierigkeiten in der Kommunikation, fehlende Kenntnisse über den anderen oder die Bezahlung einer Entschädigung. Sie können aber auch psychische Vorgänge betreffen, welche den inneren Willen der Gesuchsteller aufzeigen. In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (<ref-law>; Urteil 5A_225/2011 vom 9. August 2011 E. 5.1.1 f., in: FamPra.ch 2011 922; BGE <ref-ruling> E. 2.3 S. 152 mit Hinweisen; zu den Rügeanforderungen vgl. E. 2.2 hiervor). Rechtsfrage und damit frei zu prüfen ist hingegen, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Ehe bezwecke die Umgehung ausländerrechtlicher Vorschriften oder sei rechtsmissbräuchlich (BGE <ref-ruling> E. 2.3 S. 152).
3.4. Vorab ist festzuhalten, dass der Vorwurf der Beschwerdeführer, die Vorinstanz verfüge über keine direkten Beweise, ins Leere geht. Wie soeben dargelegt, wird der Ehewillen einer Person immer nur durch Indizien erschliessbar sein. In Bezug auf die Sachverhaltsfeststellungen wird der von der Vorinstanz dargestellte zeitliche Ablauf per se von den Beschwerdeführern nicht bestritten. Sodann ist unstrittig, dass die Beschwerdeführerin 29 Jahre jünger ist als der Beschwerdeführer.
3.4.1. Wie bereits im vorinstanzlichen Verfahren bringen die Beschwerdeführer vor, der Beschwerdeführer sei zum Zeitpunkt der Einleitung des Scheidungsverfahrens an Krebs erkrankt. Er habe damit allein fertig werden und die Beschwerdeführerin nicht damit belasten wollen, weshalb er die Scheidung eingeleitet habe. Mithin habe es nichts mit der Niederlassungsbewilligung zu tun gehabt. Er habe damals noch nicht gewusst, dass die Beschwerdeführerin schwanger sei, ansonsten er keine Scheidung in die Wege geleitet hätte.
Wie die Vorinstanz richtig festgestellt hat, konnte die Beschwerdeführerin angesichts des Geburtstermins im September 2010 bei Einleitung des Scheidungsverfahrens (15. Oktober 2009) noch gar nicht mit dem Kind schwanger sein. Überdies fällt auf, dass die Beschwerdeführer weder vor Bundesgericht noch mit der Beschwerde vom 2. Oktober 2013 ein ärztliches Dokument bezüglich der behaupteten Krebserkrankung vorgelegt haben. Sie bringen auch nicht vor, die Vorinstanz hätte diesbezüglich ein Beweismittel nicht berücksichtigt. Die Erkrankung bleibt damit blosse Behauptung, womit sich ein auffälliger zeitlicher Ablauf nicht widerlegen lässt (E. 2.2).
3.4.2. Weiter rügen die Beschwerdeführer die vorinstanzliche Feststellung als aktenwidrig, die Beschwerdeführerin habe die Zahl der Kinder aus der ersten Ehe des Beschwerdeführers nicht gewusst. Die Beschwerdeführer verweisen hierzu auf das Protokoll einer Einvernahme vom 28. April 2012 (S. 7 Ziff. 43).
Die Vorinstanz stützte sich in ihrem Urteil auf die getrennte Anhörung vom 4. September 2012. Gemäss Protokoll Ziff. 12 antwortete die Beschwerdeführerin auf die Frage, ob der Beschwerdeführer noch andere Kinder habe: "2 Töchter, 1 Sohn, alle habe ich schon einmal gesehen. Ev. hat er noch einen Sohn, diesen bin ich aber nicht sicher, ob ich den schon mal gesehen habe. Die Namen seiner Kinder habe ich vergessen." Anlässlich der Einvernahme vom 28. April 2012, welche die Beschwerdeführerin nun ins Feld führt, nannte sie zwar die korrekte Anzahl Kinder (vier), die Namen wusste sie aber nicht. Weiter gab sie vor, einen Sohn einmal gesehen zu haben, die anderen Kinder habe sie noch nie gesehen. Die Aussagen sind damit zumindest widersprüchlich und unvollständig, womit der Vorinstanz keine Willkür vorgeworfen werden kann, wenn sie feststellte, dass die Beschwerdeführerin nicht einmal die familiären Verhältnisse ihres Verlobten und früheren (langjährigen) Ehegatten kenne. Das von den Beschwerdeführern vor Bundesgericht nachgeschobene Argument, der Beschwerdeführer habe keine intensive Beziehung mit seiner Familie, widerspricht klar der Aussage des Beschwerdeführers vom 4. September 2012, dass er nach wie vor guten Kontakt zu seiner Familie habe (Protokoll Ziff. 3).
3.4.3. Bezüglich Arbeitssituation bezeichnen die Beschwerdeführer die vorinstanzliche Feststellung der gegenseitigen Unkenntnis ebenfalls als aktenwidrig. In der Einvernahme vom 23. April 2012 (S. 3 Ziff. 18) habe der Beschwerdeführer nämlich ausgeführt, was die Beschwerdeführerin im Kosovo beruflich getan habe, wisse er nicht; es habe ihn auch nie interessiert. Als sie dann in der Schweiz gewesen sei, habe sie ein Praktikum bei der Firma C._, einer Unternehmung ihrer Brüder, gemacht, wo sie heute noch arbeite, was stimme.
Wie aus dem Protokoll vom 4. September 2012 (Ziff. 18) hervor geht, antwortete er jedoch einige Monate später, zur Zeit arbeite die Beschwerdeführerin nichts, sie habe ja das Kind. Damit stellte die Vorinstanz korrekt fest, dass sich ein Widerspruch mit der Aussage der Beschwerdeführerin ergebe, welche gleichentags ausgesagt habe (Ziff. 17), sie arbeite zu 50 %. Unbestritten bleibt überdies die vorinstanzliche Feststellung, dass die Beschwerdeführerin nichts über die berufliche Tätigkeit des Beschwerdeführers wisse.
3.4.4. Schliesslich kritisieren die Beschwerdeführer, es stehe nicht fest, dass der Beschwerdeführer nicht der biologische Vater des Kindes sei. Die Vorinstanz hätte demnach nicht auf den entsprechenden Verdacht abstützen dürfen.
Wie die Beschwerdeführer selbst vorbringen, haben die zuständigen kantonalen Behörden ein Verfahren betreffend Aberkennung der Vaterschaft eingeleitet. Im Übrigen können die Beschwerdeführer aus der Tatsache, dass die Vaterschaft des Beschwerdeführers (bisher) nicht widerlegt wurde, nichts zu ihren Gunsten ableiten, gründet die Ungewissheit bezüglich biologischer Vaterschaft doch allein in der Weigerung der Beschwerdeführer, in einen Vaterschaftstest einzuwilligen. In jedem Fall ist nicht willkürlich, wenn die Vorinstanz in dieser Weigerung ein weiteres Indiz im Sinne oben dargelegter Rechtsprechung (E. 3.3) erblickte.
3.4.5. Zusätzlich zu den vorinstanzlichen Feststellungen ist auf weitere Widersprüche hinzuweisen. Wie die Beschwerdeführer selbst ausführen, verfügen sie über zwei verschiedene Wohnungen in Winterthur resp. Schaffhausen. Als Wohnadresse führen sie in der bundesgerichtlichen Beschwerde die Adresse in Winterthur auf. Noch am 4. September 2012 (Ziff. 5 f.) hatte die Beschwerdeführerin ausgesagt, sie wohne dort alleine mit ihrem Sohn. Die Wohnung sei klein, für sie beide sei es eher zu eng. Sie wollten sich etwas neues suchen. Der Beschwerdeführer wiederum gab zu Protokoll (Ziff. 6), sie würden im selben Haus, in dem im Übrigen auch die Familie D._ (Brüder und Familie der Beschwerdeführerin) wohne, eine andere Wohnung beziehen. Auch hier stimmten die Aussagen der beiden Beschwerdeführer nicht überein. Überdies behaupten die Beschwerdeführer zwar, sie würden sich seit der Geburt des Kindes im September 2010 gemeinsam um das Kind kümmern, wie sie das angesichts der zwei Wohnorte handhaben, erwähnen sie indes mit keinem Wort.
Wie die Beschwerdeführer auch vor Bundesgericht betonen, haben sie keine (sprachlichen) Verständigungsprobleme. Die Vorinstanz hat zurecht darauf hingewiesen, dass es damit um so weniger nachvollziehbar sei, dass die Beschwerdeführer so wenig voneinander wissen.
3.4.6. Die übrigen Ausführungen (u.a. in der Schweiz gebe es viele Ehen, in denen der Ehemann älter sei als die Ehefrau; der vorliegende Altersunterschied erreiche keine missbräuchlich anmutende Differenz; es gebe keine gesetzliche Pflicht bei einem DNA-Gutachten mitzuwirken; der Beschwerdeführer habe ein Recht, daran zu glauben, dass das Kind von ihm sei; die Beschwerdeführer hätten übereinstimmend ausgesagt, dass sie sich im Jahr 2000 kennen lernten) sind appellatorischer Natur (E. 2.2), worauf nicht einzutreten ist.
Den Beschwerdeführern ist es damit nicht gelungen, die von der Vorinstanz festgestellten Indizien für einen fehlenden Ehewillen zu entkräften.
3.4.7. Der Vollständigkeit halber sei erwähnt, dass die II. öffentlich-rechtliche Abteilung im Urteil 2C_303/2013 vom 13. März 2014 (E. 2.3) betreffen d die erste Ehe der Beschwerdeführer das Vorliegen einer Scheinehe für erstellt erachtet hat. Die Beschwerde gegen den Widerruf der Niederlassungsbewilligung der Beschwerdeführerin wurde lediglich aufgrund des Schweizer Bürgerrechts des Kindes, welches dieses mit der Anerkennung durch den Beschwerdeführer erwarb, gutgeheissen.
3.5. Angesichts der festgestellten Tatsachen durfte die Vorinstanz darauf schliessen, die Ehe bezwecke die Umgehung ausländerrechtlicher Vorschriften. Somit ist nicht zu beanstanden, wenn die Vorinstanz die Voraussetzungen von <ref-law> bejahte. Inwiefern die vorliegend bundesrechtskonforme Anwendung von <ref-law> zu einer Verletzung der weiteren gerügten Bestimmungen hätte führen sollen, zeigen die Beschwerdeführer nicht auf.
Die Beschwerde ist somit abzuweisen, soweit darauf eingetreten werden kann.
4.
Bei diesem Ausgang des Verfahrens haben die Beschwerdeführer für die Gerichtskosten aufzukommen (<ref-law>). Sie tragen die Kosten zu gleichen Teilen und unter solidarischer Haftbarkeit (<ref-law>). Parteientschädigungen sind keine zuzusprechen (Art. 68 Abs. 1 und 3 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3.
Dieses Urteil wird den Parteien, dem Zivilstandsamt Winterthur und dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, schriftlich mitgeteilt.
Lausanne, 15. April 2014
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Die Gerichtsschreiberin: Friedli-Bruggmann