Sachverhalt:
A.
Mit Schreiben vom 18. Januar 2017 ersuchte A._ bei der Motorfahrzeugkontrolle (MFK) des Kantons Solothurn um Umtausch seines französischen Führerausweises (Nr. xxx) in einen schweizerischen. Am 1. Februar 2017 erteilte die MFK A._ einen schweizerischen Führerausweis, während sie den französischen Ausweis vorschriftsgemäss an die Ausstellungsbehörde zurückschickte. Mit E-Mail vom 23. Februar 2018 bzw. 18. April 2018 informierte die für die Erteilung von Führerausweisen zuständige französische Behörde, die Préfecture du Haut-Rhin, die MFK, A._ habe zu Unrecht einen schweizerischen Führerausweis erworben, da sein französischer Ausweis seit dem 26. Januar 2017 nach dem französischen Punktesystem (Nullpunktsaldo) ungültig sei.
Die MFK ordnete daraufhin am 1. Mai 2018 den vorsorglichen Entzug des schweizerischen Führerausweises von A._ an, welchen sie mit Verfügung vom 7. Juni 2018 bestätigte. Am 4. Juli 2018 verfügte sie den Sicherungsentzug.
Sowohl gegen die Bestätigung des Führerausweisentzugs als auch gegen den Sicherungsentzug erhob A._ am 18. Juni 2018 bzw. am 16. Juli 2018 Beschwerde an das Verwaltungsgericht des Kantons Solothurn. Dieses wies die Beschwerden mit Entscheid vom 5. September 2018 ab.
B.
Mit Eingabe vom 8. Oktober 2018 führt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, das Urteil des Verwaltungsgerichts vom 5. September 2018 sei aufzuheben und ihm sei der Führerausweis umgehend wieder auszuhändigen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
Die MFK stellt den Antrag, die Beschwerde abzuweisen. Das Verwaltungsgericht verzichtet auf eine Vernehmlassung und beantragt ebenfalls, die Beschwerde abzuweisen. Das Bundesamt für Strassen führt aus, es stelle sich die Frage, ob der französische Führerausweis ex lege nicht mehr gültig sei, sobald der Punktestand null betrage, oder ob es für den Eintritt der Ungültigkeit eines Nachweises bedürfe. Seiner Ansicht nach ist fraglich, ob mit der E-Mail-Auskunft der französischen Behörde vom 18. April 2018 rechtsgenüglich nachgewiesen sei, dass der französische Führerausweis zum Zeitpunkt des Umtausches ungültig gewesen sei.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Entscheid betreffend Administrativmassnahmen im Strassenverkehrsrecht. Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen (vgl. <ref-law>). Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen (Art. 89 Abs. 1 Bst. a BGG) und ist als Adressat des angefochtenen Entscheids besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (Art. 89 Abs. 1 Bst. b und c BGG). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, weshalb auf die Beschwerde grundsätzlich einzutreten ist.
1.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Sachverhaltsfrage ist auch die Beweiswürdigung, die vom Bundesgericht nur unter Willkürgesichtspunkten überprüft wird (<ref-ruling> E. 4.2 S. 338).
2.
2.1. Der Beschwerdeführer ist der Auffassung, die Vorinstanz habe den Sachverhalt unrichtig festgestellt, indem sie die nicht belegte Behauptung der französischen Behörde übernommen habe, wonach ihm der Entscheid betreffend die Ungültigkeit seines französischen Führerausweises am 26. Januar 2017 per Einschreiben zugestellt und gleichentags von ihm bestätigt worden sei. Eine rechtsgenügliche Zustellung dieser Verfügung könne nicht nachgewiesen werden, womit keine Grundlage für die von der MFK angeordnete Administrativmassnahme vorliege. Die französische Behörde habe anscheinend immer noch seine alte Adresse verwendet. Sofern der Entscheid am 26. Januar 2017 tatsächlich verschickt worden sei, dürfte dies daher an seine alte Adresse in Frankreich gewesen sein. Er habe aber seit dem 29. Februar 2016 Wohnsitz in der Schweiz, weshalb er den Empfang des Entscheids gar nicht habe bestätigen können. Da ihm der Entscheid über die Ungültigkeit des französischen Führerausweises nicht rechtsgültig eröffnet worden sei, könne dieser auch keine Wirkung entfalten. Solange die Behörde die notwendigen Beweise nicht liefern könne, handle es sich bei der Aussage, wonach sein französischer Führerausweis per 26. Januar 2017 seine Gültigkeit verloren habe, um eine reine Behauptung. Die Vorinstanz habe folglich Bundesrecht verletzt, indem sie ihm dennoch seinen schweizerischen Führerausweis entzogen habe.
2.2. Die Vorinstanz hat demgegenüber erwogen, es sei unerheblich, ob dem Beschwerdeführer das Schreiben der Préfecture du Haut-Rhin zugestellt worden sei oder nicht. Massgebend sei einzig der Eintrag im französischen Führerausweisregister, in diesem sei jedenfalls die Ungültigkeit des Führerausweises verzeichnet. Die MFK habe daher zu Recht den Sicherungsentzug des Führerausweises des Beschwerdeführers angeordnet.
3.
Nach Art. 42 Abs. 1 lit. a der Verordnung vom 27. Oktober 1976 über die Zulassung von Personen und Fahrzeugen zum Strassenverkehr (Verkehrszulassungsverordnung, VZV; SR 741.6) darf ein ausländischer Motorfahrzeugführer in der Schweiz ein Motorfahrzeug führen, wenn er über einen gültigen nationalen Führerausweis verfügt. Einen schweizerischen Führerausweis benötigt ein Fahrzeugführer aus dem Ausland, wenn er seit 12 Monaten in der Schweiz wohnt und sich in dieser Zeit nicht länger als drei Monate ununterbrochen im Ausland aufgehalten hat (<ref-law>). Nach <ref-law> wird dem Inhaber eines gültigen ausländischen Ausweises der schweizerische Führerausweis der entsprechenden Kategorie erteilt, wenn er auf einer Kontrollfahrt nachweist, dass er die Verkehrsregeln kennt und Fahrzeuge der entsprechenden Kategorie sicher zu führen versteht.
Nach <ref-law> kann das ASTRA die Anerkennungsfristen für ausländische Ausweise und Kontrollschilder ändern sowie auf die Kontrollfahrt nach <ref-law> und die Theorieprüfung nach Artikel 44 Absatz 2 VZV gegenüber Führern aus Staaten verzichten, die in Bezug auf Ausbildung und Prüfung der Schweiz entsprechende Anforderungen stellen. Unbestritten ist, dass Frankreich nach der entsprechenden Länderliste des ASTRA (Anhang 2 der Beilage zum Kreisschreiben des ASTRA vom 1. Oktober 2013) zu jenen Ländern gehört, deren Ausweise grundsätzlich gegen schweizerische ausgetauscht werden, ohne dass der Inhaber eine Kontrollfahrt oder eine Theorieprüfung zu absolvieren hat. Gemäss <ref-law> ziehen die Behörden bei der Erteilung eines schweizerischen Führerausweises Ausweise ein, die von EU- oder EFTA-Staaten ausgestellt worden sind, und senden sie an die Ausstellungsbehörde zurück. Sie vermerken in Ausweisen, die von anderen Staaten ausgestellt worden sind, die Ungültigkeit für die Schweiz. Der Inhalt der ausländischen Ausweise wird registriert.
4.
4.1. Gemäss dem klaren Wortlaut von <ref-law> wird für einen Umtausch des Führerausweises ein gültiger nationaler Führerausweis verlangt. Ein ungültiger ausländischer Ausweis kann keine Grundlage für den Umtausch bzw. die Ausstellung eines schweizerischen Ausweises ohne Ablegen einer Führerprüfung bilden (vgl. <ref-law>; Urteil 1C_556/2016 vom 14. Juni 2017 E. 4.2 mit Hinweis). Diese Voraussetzung war nach Auffassung der Vorinstanz zum Zeitpunkt des Umtauschs am 1. Februar 2017 nicht (mehr) gegeben.
4.2. Gemäss dem im Verwaltungsverfahren geltenden Untersuchungsgrundsatz ist es Sache der Behörde und nicht der Parteien, den Sachverhalt festzustellen und dazu soweit nötig Beweis zu erheben (vgl. § 14 Abs. 1 des Gesetzes vom 15. November 1970 über den Rechtsschutz in Verwaltungssachen des Kantons Solothurn; [Verwaltungsrechtspflegegesetz; BGS 124.11]). Der Untersuchungsgrundsatz ändert hingegen an der objektiven Beweislast nichts. Demnach hat diejenige Partei die Folgen der Beweislosigkeit eines Sachumstands zu tragen, die daraus Vorteile für sich ableitet (zur Anwendbarkeit von <ref-law> auf öffentlichrechtliche Verfahren vgl. <ref-ruling> E. 6.3.1 S. 299).
Im hier zu beurteilenden Fall will der Beschwerdeführer den Entzug des umgetauschten schweizerischen Führerausweis verhindern. Tatbestandsvoraussetzung für den Umtausch ist, wie in der vorstehenden E. 4.1 ausgeführt, ein gültiger ausländischer Führerausweis. Die objektive Beweislast hierfür liegt somit bei ihm. Bleibt trotz der behördlichen Abklärungen unsicher, ob er über einen gültigen französischen Führerausweis verfügt, hat er keinen Anspruch auf Ausstellung eines schweizerischen Führerausweises ohne eine Kontrollfahrt absolviert zu haben.
4.3. Die MFK hat bei den französischen Behörden die erforderlichen Abklärungen getroffen. auch der Beschwerdeführer macht keine Verletzung des Untersuchungsgrundsatzes geltend. Die Abklärungen haben zum Ergebnis geführt, dass der französische Führerausweis des Beschwerdeführers gemäss den Angaben der französischen Behörde am 26. Januar 2017 seine Gültigkeit verloren hatte, weil seine Anzahl Punkte bei null gewesen ist ("pour solde de points nul"; vgl. Art. L223-1 des Code de la route). Dies ergibt sich auch aus dem aktenkundigen Auszug des französischen Führerausweisregisters vom 5. März 2018. Ausserdem haben die französischen Behörden der MFK mitgeteilt, die Ungültigkeit seines Führerausweises sei dem Beschwerdeführer mit eingeschriebenem Brief mitgeteilt worden und dieser habe den Empfang dieses Schreibens bestätigt, doch verfügten sie über keine Kopie davon.
Der Beschwerdeführer hält dem entgegen, die Mitteilung betreffend die Ungültigkeit seines französischen Führerausweises sei ihm nicht zugestellt worden und sei daher ungültig; allenfalls sei dieser Entscheid an seine frühere Adresse in Colmar (F) verschickt worden. Es sei sehr eigenartig, dass die französischen Behörden über keine Kopie der angeblichen Empfangsbestätigung verfügen würden. Dagegen bestreitet er nicht - oder jedenfalls nicht ausdrücklich - in einer Weise gegen das französische Strassenverkehrsrecht verstossen zu haben, die nach dem dortigen Recht zu einem Entzug des Führerausweises führt.
4.4. Das Bundesgericht prüft die vorinstanzliche Beweiswürdigung nur auf Willkür hin (oben E. 1.2). Beim soeben dargestellten Beweisergebnis ist es offensichtlich nicht willkürlich, wenn die Vorinstanz das Tatbestandsmerkmal des gültigen französischen Führerausweises als nicht gegeben erachtete. Dass dieses Ausweispapier des Beschwerdeführers zum Zeitpunkt des Austausches seine Gültigkeit verloren hatte, erscheint kaum zweifelhaft. Gewisse Unklarheiten verbleiben lediglich betreffend der Eröffnung dieses Entscheids. Allerdings zeigt der Beschwerdeführer nicht auf, dass der Führerausweis nach französischem Recht weiter gelten würde, wenn dessen Ungültigkeit nicht rechtsgenüglich eröffnet worden sein sollte; er behauptet dies nicht einmal. Ebenso wenig belegt er, dass er sich vor seinem Wegzug in die Schweiz bei den französischen Behörden abgemeldet hätte, so dass diese die Ungültigkeit seiner bisherigen Wohnadresse hätten kennen müssen.
4.5. Zusammenfassend ergibt sich, dass die Vorinstanz den Sachverhalt ausreichend abgeklärt hat und sehr erhebliche Zweifel an der Gültigkeit des französischen Ausweises des Beschwerdeführers bestehen. Da dieser die Beweislast für die Gültigkeit des französischen Ausweises trägt, ist es nicht zu beanstanden, dass die Vorinstanz das Tatbestandselement des gültigen ausländischen Führerausweises verneint und folglich den Umtausch in einen schweizerischen Führerausweis verweigert bzw. diesen wieder entzogen hat.
5.
Nach dem Gesagten erweist sich die Beschwerde als unbegründet und ist abzuweisen. Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird dem Beschwerdeführer, dem Bau- und Justizdepartement des Kantons Solothurn, dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Strassen, Sekretariat Administrativmassnahmen, schriftlich mitgeteilt.
Lausanne, 17. Januar 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Sauthier