Faits:
A.
B._, ressortissante de Côte d'Ivoire née en 1983, a déposé le 19 avril 2010 une demande d'autorisation d'entrée en Suisse auprès de l'Ambassade de Suisse à Abidjan en vue d'épouser A._, ressortissant suisse né en 1952. Le 18 juin 2010, elle a également déposé une demande d'exécution de la procédure préparatoire au mariage. Le fiancé a été entendu le 2 septembre 2010 à l'Office de l'état civil de Lausanne. Quant à la fiancée, elle a été auditionnée le 30 septembre 2010 à l'Ambassade de Suisse à Abidjan.
B.
B.a. Par décision du 3 février 2011, l'Office de l'état civil de Lausanne a refusé de prêter son concours à la célébration du mariage, en raison de l'intention manifeste de la fiancée d'abuser de cette institution dans le but d'éluder les dispositions sur l'admission et le séjour des étrangers. Le recours formé par le fiancé à l'encontre de cette décision a été déclaré irrecevable le 21 mars 2011, faute du paiement de l'avance de frais.
Le 8 août 2011, le Service de la population du canton de Vaud (ci-après: SPOP) a refusé de délivrer à la fiancée une autorisation d'entrée en Suisse en vue du mariage.
Le 30 septembre 2011, les fiancés ont demandé à la Direction de l'état civil de reconsidérer sa décision du 3 février 2011. Le même jour, ils ont également demandé au SPOP de délivrer une autorisation de séjour en faveur de la fiancée, exposant qu'elle avait dans l'intervalle fui son pays en raison de la guerre civile et de massacres commis dans son quartier, et s'était réfugiée en Suisse.
Le 5 octobre 2011, la Direction de l'état civil a indiqué aux intéressés qu'ils devaient présenter une nouvelle demande d'ouverture d'un dossier de mariage, la précédente procédure ayant été close par décision du 3 février 2011, et le recours déposé contre cette dernière ayant été déclaré irrecevable.
B.b. A la suite de la demande déposée le 12 octobre 2011, une nouvelle procédure préparatoire de mariage a été ouverte. Les fiancés ont été reçus le 15 décembre 2011 par l'Office de l'état civil pour les formalités du mariage et ont été auditionnés.
Estimant se trouver en présence d'un projet de mariage de complaisance au sens de l'<ref-law>, l'Office de l'état civil a transmis, le 23 décembre 2011, le dossier de mariage à la Direction de l'état civil pour qu'elle se détermine.
Le 31 janvier 2012, la Direction de l'état civil a relevé que la fiancée ne disposait d'aucun titre de séjour en Suisse. Elle a imparti aux fiancés un délai de 30 jours pour démontrer la légalité du séjour conformément aux <ref-law> et 66 al. 2 let. e OEC, à défaut de quoi une décision de non-entrée en matière serait rendue.
Par courrier du 24 février 2012, le SPOP a informé les fiancés du fait qu'il avait décidé de ne pas octroyer une " tolérance de séjour " à la fiancée. Saisie d'un recours contre cette décision, la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud l'a annulée pour défaut de motivation par arrêt du 25 avril 2012 et a renvoyé le dossier au SPOP pour nouvelle décision.
B.c. Le 9 juillet 2012, la Direction de l'état civil a adressé au SPOP une copie du dossier de mariage ainsi que des principales pièces de la précédente procédure de mariage. Elle a relevé divers éléments qui montraient, selon elle, qu'il existait toujours des indices concluants et manifestes d'un mariage de complaisance.
Le 30 juillet 2012, le SPOP a informé les fiancés de son intention de refuser l'octroi d'une autorisation de séjour en vue de mariage à la fiancée, et de prononcer son renvoi de Suisse. Tant les fiancés que la Direction de l'état civil se sont déterminés. Celle-ci a notamment fait valoir, par courrier du 21 septembre 2012, que la fiancée ne disposait toujours pas de titre de séjour légal. La Direction de l'état civil a précisé que, au cas où elle en obtiendrait un, elle préavisait d'ores et déjà négativement sur la célébration du mariage, tout en ajoutant que, si l'Office de l'état civil était d'un avis contraire, il pourrait autoriser cette célébration.
Le 3 octobre 2012, le SPOP a refusé de délivrer une autorisation de séjour pour le motif, d'une part, qu'un faisceau d'indices ressortant de la procédure de mariage permettait de considérer qu'il s'agissait d'un cas d'abus de droit au mariage et, d'autre part, que l'intéressée était venue en Suisse avec des faux documents, sans être au bénéfice d'un quelconque visa, et qu'elle y avait séjourné illégalement. Le SPOP a également constaté que son départ de Suisse était possible, licite et exigible, et lui a imparti un délai de trois mois pour quitter le territoire.
Le 30 octobre 2012, la fiancée a recouru contre cette décision devant la Cour de droit administratif et public, qui a rejeté le recours par arrêt du 9 avril 2013. Un recours en matière de droit public à l'encontre de cet arrêt est actuellement pendant devant la IIème Cour de droit public du Tribunal fédéral; celle-ci a accordé l'effet suspensif au recours par ordonnance du 22 mai 2013 (dossier n° 2C_437/2013).
B.d. Par décision du 4 octobre 2012, l'Office de l'état civil a mis fin à la procédure préparatoire du mariage conformément à l'<ref-law>, la fiancée n'ayant pas établi la légalité de son séjour en Suisse, et a subsidiairement refusé son concours à la célébration du mariage en vertu de l'<ref-law>, l'abus de droit au mariage étant manifeste en l'espèce.
Par acte du 6 novembre 2012, les fiancés ont recouru contre cette décision devant la Cour de droit administratif et public. Ils ont conclu à son annulation et au renvoi de la cause à l'autorité inférieure pour nouvelle instruction et nouvelle décision. La Direction de l'état civil, agissant en tant qu'autorité concernée, s'est déterminée le 10 décembre 2012; agissant en son nom et au nom de l'Office de l'Etat civil, elle a conclu au rejet du recours.
Par arrêt du 9 avril 2013, la Cour de droit administratif et public a rejeté le recours et confirmé la décision de l'Office de l'état civil du 4 octobre 2012.
C.
Par acte du 10 mai 2013, les fiancés interjettent un " recours en matière de droit public " au Tribunal fédéral. Ils concluent à l'annulation de l'arrêt rendu par la Cour de droit administratif et public le 9 avril 2013, et au renvoi de la cause à cette autorité pour complément d'instruction et nouvelle instruction dans le sens des considérants.
Des réponses n'ont pas été requises.

Considérant en droit:
1.
1.1. L'arrêt attaqué, qui porte sur le refus de poursuivre la procédure préparatoire du mariage (<ref-law>) et de concourir à la célébration du mariage (<ref-law>), constitue une décision finale au sens de l'<ref-law> (arrêt 5A_612/2012 du 19 novembre 2012 consid. 1), prise sur recours par un tribunal supérieur statuant en dernière instance cantonale (art. 75 al. 1 et 2 LTF), en application de normes de droit public, notamment de droit des étrangers, dans une matière connexe au droit civil (<ref-law>; arrêt 5A_814/2011 du 17 janvier 2012 consid. 1, non publié in <ref-ruling>; arrêt 5A_612/2012 du 19 novembre 2012 consid. 1). La décision entreprise est de nature non pécuniaire (<ref-law> a contrario). Le présent recours est interjeté dans le respect du délai légal (<ref-law>) et de la forme prévue par l'<ref-law>, par des parties qui ont succombé dans leurs conclusions prises devant l'autorité précédente et ont un intérêt digne de protection à son annulation ou à sa modification (<ref-law>).
Les recourants ont intitulé leur mémoire " recours en matière de droit public ". Cela étant, le recours doit être traité en tant que recours en matière civile au sens des <ref-law>. L'intitulé erroné d'un recours ne porte pas préjudice à ses auteurs (<ref-ruling> consid. 1.2 p. 382; <ref-ruling> consid. 6 p. 279), pour autant qu'ils invoquent des griefs admissibles dans le cadre de la voie de droit qui est ouverte (<ref-law>).
1.2. Compte tenu des exigences de motivation posées, sous peine d'irrecevabilité, à l'<ref-law>, le Tribunal fédéral n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une juridiction de première instance, toutes les questions juridiques pouvant se poser lorsqu'elles ne sont plus discutées devant lui (<ref-ruling> consid. 1.2 p. 152). Il ne connaît de la violation de droits fondamentaux que si ce grief a été soulevé et dûment motivé par le recourant ( <ref-law>; <ref-ruling> consid. 3 p. 351-352 et les références).
2.
Selon la cour cantonale, dès lors que la fiancée s'est vu refuser une autorisation de séjour par le SPOP, l'Office de l'état civil n'avait pas d'autre choix que de mettre un terme à la procédure préparatoire du mariage en application de l'<ref-law>. La Cour de droit administratif et public ne s'est pas prononcée sur la question de savoir si l'Office de l'état civil aurait dû attendre l'entrée en force de la décision du SPOP avant de prendre sa décision, estimant que, de toute manière, celle-ci avait refusé à juste titre son concours à la célébration du mariage sur la base de l'<ref-law>.
Concernant précisément le refus de célébrer le mariage (<ref-law>), l'autorité précédente a repris à l'appui de son raisonnement les éléments de fait développés par l'Office de l'état civil. Elle a acquis la conviction, sur la base d'un faisceau d'indices, que la fiancée avait en réalité pour but d'obtenir, au moyen du mariage, une autorisation de séjour. Elle a constaté qu'il existait une très grande différence d'âge entre les fiancés, à savoir 31 ans, que leur rencontre avait été organisée par un cousin de la fiancée vivant en Suisse à l'époque des faits, que la fiancée était entrée en Suisse illégalement au moyen de passeurs et que chacun ne connaissait que très peu d'éléments de la vie de l'autre. La fiancée n'a pas connaissance du montant du salaire de son fiancé, ni de ce qu'il fait concrètement dans la vie, pas plus qu'elle ne sait avec qui il a été marié précédemment; ce dernier ne s'est pas non plus intéressé à la " vie antérieure " de sa fiancée. Les juges cantonaux ont retenu que la fiancée avait des difficultés à s'exprimer en français, n'avait pas toujours compris les questions qui lui ont été posées, ni même été en mesure de donner le nom de l'école où elle est censée suivre des cours à raison de trois fois par semaine. En outre, les fiancés n'auraient pas d'autre projet commun que de se marier, pas plus qu'ils ne partageraient d'intérêt commun.
Tenant compte de l'ensemble de ces éléments, la cour cantonale a considéré que la recourante entendait éluder les règles sur le séjour des étrangers et non fonder une communauté conjugale. Le fait que le projet de mariage existe depuis plus d'une année et qu'il n'a pas été abandonné ne serait pas déterminant, car on peut concevoir une volonté durable des intéressés d'éluder les dispositions de la LEtr. Pour ces motifs, les juges cantonaux ont confirmé la décision de l'Office de l'état civil.
3.
3.1. Les recourants critiquent la manière dont l'autorité précédente a appliqué l'<ref-law>. Selon eux, c'est à tort qu'elle a confirmé la clôture de la procédure préparatoire du mariage. Cette décision aurait été prise pour le motif que le SPOP a refusé de délivrer une autorisation de séjour; or ce refus découlerait du fait que le SPOP a retenu l'existence d'indices d'abus de droit au mariage.
Les recourants s'en prennent dans un deuxième grief au refus du SPOP d'octroyer une autorisation de séjour. Ils estiment que leur demande aurait dû être approuvée, faute par l'autorité de police des étrangers d'avoir apporté la preuve de la commission d'un abus de droit au mariage.
Ils soutiennent par ailleurs que l'autorité précédente a constaté les faits et apprécié les preuves de manière arbitraire (art. 9 Cst.) en ce qui concerne l'abus du droit au mariage (<ref-law>), et critiquent en particulier la rigueur avec laquelle l'autorité cantonale a fait application des indices pris en compte pour apprécier l'existence ou non d'un abus du droit. Cette rigueur serait inacceptable et l'autorité aurait dû rapporter la preuve de la commission de l'abus de droit. A leurs yeux, ni la méconnaissance mutuelle, ni l'absence de projet commun autre que le mariage ne permet de retenir l'existence d'un abus de droit. Ils exposent que, si leur différence d'âge est importante, elle n'a rien d'anormal, dans la mesure où l'on ne se trouve pas dans la situation d'une personne de 18 ans qui souhaite épouser un octogénaire. Ils ajoutent que " surchargé par ses activités professionnelles, [le recourant] a cherché à rompre sa solitude via une petite annonce. Le procédé n'a rien d'insolite ". S'agissant de l'entrée en Suisse de la fiancée, ils précisent que " chercher à sauver sa peau en recourant à de faux papiers et à un passeur n'a rien de scandaleux ", et exposent qu'elle a spontanément déclaré à l'administration son entrée illégale, qui a fait suite à des troubles graves et des massacres qui auraient eu lieu dans son pays. Enfin, en ce qui concerne leur prétendue absence de projet commun autre que de se marier, les recourants soutiennent que la manière dont ils ont été interrogés n'avait rien de bienveillant et ne les incitait pas à une grande loquacité, ce qui pourrait expliquer un certain mutisme de leur part. Dès lors et fondée sur des faits non établis, l'arrêt entrepris violerait l'<ref-law>.
3.2.
3.2.1. Le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (<ref-law>), à moins que ceux-ci n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). Le recourant qui soutient que les faits ont été établis de manière manifestement inexacte (<ref-law>), à savoir que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.4.1 p. 39; <ref-ruling> consid. 1.2.2 p. 252), doit démontrer, par une argumentation précise, en quoi consiste la violation; il ne saurait se borner à critiquer la décision attaquée comme il le ferait en instance d'appel, où l'autorité de recours jouit d'une libre cognition; il ne peut, en particulier, se contenter d'opposer sa thèse à celle de la juridiction cantonale. Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 3; <ref-ruling> consid. 4.1 p. 588 s.; <ref-ruling> consid. 1.3 p. 261). Selon la jurisprudence, il n'y a arbitraire en matière d'appréciation des preuves et de constatation des faits que lorsque le juge ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'il se trompe manifestement sur son sens et sa portée ou encore lorsque, en se fondant sur les éléments recueillis, il en tire des constatations insoutenables (<ref-ruling> consid. 4.2 p. 560; <ref-ruling> consid. 4.3 p. 62; <ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 1b p. 30).
3.2.2. En vertu de l'<ref-law>, l'officier de l'état civil est compétent pour célébrer le mariage. Il peut refuser son concours lorsque deux conditions cumulatives sont remplies (<ref-law>). D'une part, les intéressés ne doivent avoir aucune volonté de fonder une communauté conjugale. D'autre part, ils doivent avoir l'intention d'éluder les dispositions sur l'admission et le séjour des étrangers. La réalisation de ces deux conditions doit être manifeste (arrêts 5A_901/2012 du 23 janvier 2013 consid. 4.2.1 et les références; 5A_225/2011 du 9 août 2011 consid. 5.1.1). De jurisprudence constante, la volonté de fonder une communauté conjugale est un élément intime qui, par la nature des choses, ne peut pas être prouvé directement. Le plus souvent, l'abus ne pourra être établi qu'au moyen d'un faisceau d'indices, notamment une grande différence d'âge entre les fiancés, l'impossibilité pour ceux-ci de communiquer, une méconnaissance réciproque, le paiement d'une somme d'argent, un mariage contracté alors qu'une procédure de renvoi est en cours ou que l'un des fiancés séjourne illégalement en Suisse (<ref-ruling> consid. 2b p. 295; arrêt 5A_901/2012 du 23 janvier 2013 consid. 4.2.1).
La jurisprudence retient que les constatations portant sur des indices peuvent concerner des circonstances externes, tout comme des éléments d'ordre psychique, relevant de la volonté interne. Il s'agit, dans les deux cas, de constatations de fait (<ref-ruling> consid. 2.3 p. 152 et les arrêts cités) qui lient le Tribunal fédéral, sauf si elles ont été établies de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (arrêt 5A_901/2012 du 23 janvier 2013 consid. 4.2.2; arrêt 5A_201/2011 du 26 juillet 2011 consid. 3.1.2).
3.3. Lorsqu'ils critiquent le refus du SPOP de délivrer une autorisation de séjour en vue de mariage, les recourants perdent de vue que cette question ne saurait être examinée dans le cadre du présent recours, puisqu'elle concerne la décision rendue par le SPOP et non l'arrêt entrepris, qui traite exclusivement de la décision prise par l'Office de l'état civil. La décision du SPOP, en tant qu'elle a été confirmée par la Cour de droit administratif et public, fait d'ailleurs l'objet du recours dont est saisie la IIème Cour de droit public du Tribunal fédéral (dossier n° 2C_437/2013).
S'agissant de la constatation des faits, les recourants n'expliquent en définitive pas en quoi elle aurait été effectuée de manière insoutenable. Ils précisent les circonstances de la venue en Suisse de la fiancée, mais ne nient pas que cette arrivée était illégale ni que, par le mariage, elle souhaite régulariser sa situation. En outre, en tant qu'ils s'expliquent sur leur absence de projet commun autre que le mariage, les recourants invoquent des faits qui ne ressortent pas de l'arrêt entrepris; ils se contentent d'alléguer qu'ils n'auraient pas été auditionnés de manière bienveillante.
Lorsqu'ils critiquent la " rigueur " avec laquelle le système du faisceau d'indices aurait été appliqué pour retenir l'abus de droit au mariage, les recourants perdent de vue que les juges cantonaux, pour forger leur conviction, ont pris en considération de multiples indices pertinents (cf. supra consid. 2), dont la nature correspond à ceux mentionnés par la jurisprudence. Au surplus, on ne discerne pas en quoi ils auraient appliqué la jurisprudence de manière trop rigoureuse. Ils ont notamment tenu compte de l'âge des fiancés, de la difficulté qu'ils ont à communiquer, du fait que chacun ne connaît que très peu la vie de l'autre, et que la fiancée est entrée illégalement en Suisse. Force est dès lors de constater que par son argumentation essentiellement appellatoire, le recourant ne démontre pas que l'autorité a abusé de son pouvoir d'appréciation.
3.4. Pour ces motifs, c'est à bon droit que la Cour de droit administratif et public a retenu que la volonté d'éluder les dispositions sur l'admission et le séjour des étranger était réalisée, et confirmé le refus de l'Office de l'état civil de célébrer le mariage, ce qui scelle déjà le sort du recours à cet égard. Par conséquent il ne s'impose pas d'examiner plus avant la condition de l'autorisation de séjour (<ref-law>).
4.
Les recourants soutiennent finalement que la norme de l'<ref-law> violerait en tant que telle leur droit au mariage, l'interdiction des discriminations et leur liberté individuelle. Ils affirment qu'il existe deux réglementations du mariage, soit une pour les citoyens suisses, régie par les dispositions du Code civil, et une autre pour les étrangers, " imposant, en l'état actuel, que les fiancés se connaissent depuis longtemps, qu'il n'existe pas entre eux une grande différence d'âge, qu'il n'y ait pas appartenance à un groupe marginal, qu'il n'y ait pas de difficultés de communications, qu'ils connaissent tout des conditions de vie de leur futur partenaire, etc. ". A leurs yeux, cela serait discriminatoire et ne respecterait pas le droit au mariage.
4.1. Le droit au mariage, garanti par les art. 14 Cst. et 12 CEDH, protège les particuliers contre les mesures étatiques qui limiteraient de manière injustifiée la faculté de se marier et le choix du conjoint (arrêt 5A_901/2012 du 23 janvier 2013 consid. 3.1). Ce droit fondamental n'a pas une portée absolue. Il peut faire l'objet de restrictions, pour autant que celles-ci ne portent pas atteinte à l'essence même de ce droit, qu'elles reposent sur une loi au sens formel, soient justifiées par un motif d'intérêt public et respectent le principe de la proportionnalité (arrêts 5A_901/2012 du 23 janvier 2013 consid. 3.1; 5A_225/2011 du 9 août 2011 consid. 5.1).
Lorsqu'ils se plaignent d'une discrimination avec les couples de fiancés suisses, les recourants omettent de prendre en considération que l'<ref-law> n'est pas applicable à ces derniers. Cette disposition ne peut être pertinente que pour un fiancé étranger dont le législateur entend sanctionner un abus dans le droit au mariage, en tant que sa volonté n'est en réalité pas de se marier, mais bien d'obtenir par ce biais un droit à un séjour en Suisse. Or, seul le droit au mariage comme véritable but de la démarche est protégé; la restriction découlant de l'<ref-law> ne porte pas atteinte à l'essence de ce droit et ne vise qu'à faire obstacle à un exercice abusif du droit au mariage (arrêt 5A_901/2012 du 23 janvier 2013 consid. 3.2.2). Pour ces motifs, le grief doit être rejeté.
4.2. Enfin, autant que les recourants paraissent soulever le grief de violation de la liberté individuelle, leur critique est irrecevable faute de remplir les exigences en matière de motivation (<ref-law>; cf. supra consid. 2). Au demeurant, on ne discerne pas en quoi l'invocation de la garantie de la liberté personnelle serait ici pertinente.
5.
Vu ce qui précède, le recours doit être rejeté dans la mesure de sa recevabilité. Les frais judiciaires sont mis solidairement à la charge des recourants qui succombent (art. 66 al. 1 et 5 LTF). L'Office de l'état civil, qui n'a pas été invité à déposer des observations, n'a pas droit à l'allocation de dépens (art. 68 al. 2 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis solidairement à la charge des recourants.
3.
Le présent arrêt est communiqué aux recourants, à l'Office de l'état civil de Lausanne et à la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud.
Lausanne, le 22 août 2013
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président: von Werdt
La Greffière: Bonvin