Entzug eines schweizerischen Reisepapiers, hat sich ergeben:
A.- Im Januar 1975 gelangte der aus Bulgarien stammende X._, geboren 1943, im Rahmen einer besonderen Hilfsaktion zusammen mit seiner damaligen Ehefrau in die Schweiz, wo er als Flüchtling anerkannt wurde. In der Folge stellte ihm das Bundesamt für Flüchtlinge (im Folgenden: Bundesamt) einen Reiseausweis für Flüchtlinge aus, dessen Gültigkeitsdauer regelmässig verlängert wurde, letztmals bis zum 2. April 1993.
Mit Urteil des Geschworenengerichts des Kantons Zürich vom 24. Januar 1986 bzw. 25. März 1988 wurde X._ unter anderem für die Dauer von zehn Jahren des Landes verwiesen. Nach seiner bedingten Entlassung aus dem Strafvollzug reiste X._ in die Bundesrepublik Deutschland aus, von wo er am 8. März 1990 in die Schweiz zurückgeschoben wurde, wobei der Vollzug der gerichtlich angeordneten Landesverweisung wegen Unmöglichkeit für die Dauer der Probezeit aufgeschoben wurde.
B.- Das Bundesamt für Flüchtlinge widerrief am 10. Mai 1993 das X._ gewährte Asyl, wobei ihm gleichzeitig die Flüchtlingseigenschaft aberkannt und sein Reiseausweis zu den Akten genommen wurde. Das Bundesamt erwog im Wesentlichen, auf Grund der politischen Veränderungen in Bulgarien könne X._ nicht mehr länger ablehnen, den Schutz seines Heimatlandes in Anspruch zu nehmen. Es sei ihm nun wieder zumutbar, sich um einen gültigen heimatlichen Pass zu bemühen. Diese Verfügung erwuchs unangefochten in Rechtskraft.
Mit Schreiben vom 18. Juni 1993 und 2. Juli 1993 ersuchte X._ um Rückgabe seines Flüchtlingspasses.
In der Folge reichte er dem Bundesamt eine Bescheinigung des bulgarischen Justizministeriums vom 7. Juli 1993 ein, wonach er von der bulgarischen Staatsangehörigkeit befreit sei. Das Bundesamt erteilte ihm daraufhin einen während zwei Jahren gültigen Pass für Ausländer (Nr. ...). Am 18. Juli 1995 verlängerte das Bundesamt die Gültigkeit dieses Passes bis zum 19. Juli 1997 und forderte X._ gleichzeitig auf, sich nunmehr ernsthaft um den Erhalt eines heimatlichen Ausweises zu bemühen. Mit Schreiben vom 10. November 1995 wies das Bundesamt X._ an, seine Wiedereinbürgerung zu beantragen.
Abklärungen beim Ministerium für auswärtige Angelegenheiten in Sofia hätten nämlich ergeben, dass ihm jederzeit die Möglichkeit offen stehe, sich in Bulgarien wieder einbürgern zu lassen. Zugleich verfügte das Bundesamt den Entzug des Passes für Ausländer.
Am 27. August 1996 verlängerte das Bundesamt den Pass für Ausländer um weitere drei Jahre. Auf Gesuch von X._ um Abgabe eines Reiseausweises für Flüchtlinge hin wurde ihm am 9. September 1997 ein neuer Pass für Ausländer (Nr. ...) ausgestellt, da er das alte Dokument offenbar gewaschen hatte.
C.- X._ stellte am 26. April 1999 ein Gesuch um Ausstellung eines neuen schweizerischen Reisepapiers. Mit Schreiben vom 21. Juni 1999 forderte das Bundesamt ihn auf, den aktuellen Pass für Ausländer einzureichen. X._ teilte daraufhin dem Bundesamt mit, er habe sich in der Vergangenheit vergeblich um einen heimatlichen Reisepass bemüht.
Mit Schreiben vom 1. September 1999 teilte das Bundesamt X._ mit, seine Abklärungen bei der Schweizer Vertretung in Bulgarien hätten ergeben, dass er im Besitze eines bulgarischen Passes sei. Seinem Gesuch um Ausstellung eines Passes könne aus diesem Grund nicht entsprochen werden. Gleichzeitig ersuchte ihn das Bundesamt noch einmal um Einreichung des Passes für Ausländer. In seiner Eingabe vom 9. September 1999 verneinte X._, dass ihm ein bulgarischer Pass ausgehändigt worden sei, und machte geltend, er habe den verlangten Pass für Ausländer retourniert.
Am 6. Oktober 1999 teilte das Bundesamt X._ mit, seinem Gesuch um Ausstellung eines schweizerischen Ersatzreisepapiers könne nicht entsprochen werden, da er zweifelsfrei im Besitze eines am 6. Februar 1995 ausgestellten bulgarischen Passes mit der Nummer ... sei. Somit gelte er nicht als schriftenlos im Sinne von Art. 6 Abs. 1 der Verordnung vom 11. August 1999 über die Abgabe von Reisepapieren an ausländische Personen (RPAV; SR 143. 5). Mit Telefax vom 17. Oktober 1999 bestritt X._ erneut, Inhaber des fraglichen bulgarischen Ausweises zu sein.
Am 21. Oktober 1999 verfügte das Bundesamt, dass der Pass für Ausländer Nr. ... entzogen werde und dem Bundesamt innerhalb von 5 Tagen bzw. bei Verlust unmittelbar nach einem allfälligen Wiederauffinden zuzustellen sei.
Eine Beschwerde gegen diese Verfügung wies das Eidgenössische Justiz- und Polizeidepartement mit Entscheid vom 6. April 2000 ab.
D.- Dagegen hat X._ am 17. April 2000 beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben. Das Eidgenössische Justiz- und Polizeidepartement beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei.
Das Bundesamt verzichtet in seiner verspätet eingereichten Vernehmlassung auf einen Antrag.
E.- Am 15. Mai 2000, 15. Juni 2000, 26. Juni 2000 sowie am 29. Juni 2000 reichte X._ weitere Eingaben ein. Mit Schreiben vom 13. Juli 2000 übermittelte die Direktion für Soziales und Sicherheit des Kantons Zürich, Fremdenpolizei, eine an das Bundesgericht adressierte Eingabe X._s vom 29. Juni 2000.

Das Bundesgericht zieht in Erwägung:
1.-a) Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob es auf eine Beschwerde eintreten kann (<ref-ruling> E. 1 S. 83; <ref-ruling> E. 1a S. 299, mit Hinweisen).
b) Gemäss Art. 108 Abs. 2 OG hat die Verwaltungsgerichtsbeschwerde unter anderem die Begehren und deren Begründung zu enthalten. An diese sind nach der bundesgerichtlichen Rechtsprechung keine allzu hohen Anforderungen zu stellen, da im verwaltungsgerichtlichen Beschwerdeverfahren das Bundesgericht das Recht von Amtes wegen anzuwenden hat (Art. 114 Abs. 1 OG). Es genügt, wenn aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird (<ref-ruling> E. 2 S. 135, mit Hinweis).
Der Beschwerdeführer stellt in seiner Verwaltungsgerichtsbeschwerde kein konkretes Rechtsbegehren. Seiner Begründung lässt sich aber entnehmen, dass er die Auffassung der Vorinstanz, er sei nicht schriftenlos im Sinne der einschlägigen Gesetzesbestimmungen, bestreitet. Weiter rügt der Beschwerdeführer zumindest sinngemäss eine unrichtige und unvollständige Feststellung des rechtserheblichen Sachverhaltes.
Damit genügt seine Eingabe den Formerfordernissen von Art. 108 Abs. 1 und 2 OG und es ist grundsätzlich darauf einzutreten.
Im Verfahren der Verwaltungsgerichtsbeschwerde bildet die Verfügung als Anfechtungsobjekt den Ausgangspunkt des Verfahrens und zugleich den Rahmen und die Begrenzung des Streitgegenstands (<ref-ruling> E. 1d S. 417 f.). Da der Entzug des Passes für Flüchtlinge nicht Gegenstand des vorinstanzlichen Verfahrens war, kann auf die Verwaltungsgerichtsbeschwerde nicht eingetreten werden, soweit der Beschwerdeführer geltend macht, der Pass für Flüchtlinge sei ihm zu Unrecht entzogen worden.
c) Im Fremdenpolizeirecht stellt das Bundesgericht grundsätzlich auf die aktuellen tatsächlichen und rechtlichen Umstände ab. Da als Vorinstanz nicht eine richterliche Behörde (vgl. Art. 105 Abs. 2 OG) entschieden hat und auch sonst keine Gründe für eine Ausnahme vorliegen, ist somit der Sachverhalt massgeblich, wie er sich im Zeitpunkt des bundesgerichtlichen Urteils ergibt (Art. 104 lit. b OG, Art. 105 Abs. 1 OG; <ref-ruling> E. 1b S. 4, mit Hinweisen).
Nach der bundesgerichtlichen Rechtsprechung können nach Ablauf der Beschwerdefrist, unter Vorbehalt von Art. 108 Abs. 3 OG, keine neuen Eingaben mehr eingereicht werden, es sei denn, sie dienten dazu, Vorbringen der Gegenpartei in einer vom Bundesgericht zugelassenen Replik zu widerlegen (unveröffentlichtes Urteil vom 25. Februar 2000 i.S. B.H.; <ref-ruling> E. 3c, S. 249 f.; <ref-ruling> E. 1 S. 89). Gemäss Art. 110 Abs. 4 OG findet ein zweiter Schriftenwechsel nur ausnahmsweise statt, vor allem dann, wenn in der Vernehmlassung der Gegenpartei neue tatsächliche Behauptungen aufgestellt werden, die für die Entscheidung von wesentlicher Bedeutung sind (<ref-ruling> E. 1 S. 323 mit Hinweisen). Im vorliegenden Fall wurde kein zweiter Schriftenwechsel angeordnet und im Übrigen von den Parteien auch nicht verlangt. Aus diesem Grund sind die vom Beschwerdeführer nach Ablauf der Beschwerdefrist eingereichten Eingaben vom 15. Mai 2000, 15. Juni 2000,
26. Juni 2000 sowie vom 29. Juni 2000 unbeachtlich.
d) Das Bundesamt hat seine Vernehmlassung verspätet übermittelt. Es hat zwar auf eine Stellungnahme verzichtet, aber zum Fall zugehörige Akten eingereicht. Das Bundesgericht wendet auf Verwaltungsgerichtsbeschwerde hin das Recht von Amtes wegen an (Art. 114 Abs. 1 OG; <ref-ruling> E. 2b S. 29, mit Hinweisen) und prüft vorliegendenfalls den Sachverhalt frei (vgl. E. 1c). Dem Bundesgericht ist daher nicht verwehrt, die erwähnten Akten, die es auch von Amtes wegen beiziehen könnte, zu berücksichtigen.
2.- a) Gemäss Art. 1 Abs. 2 RPAV gibt das Bundesamt für Flüchtlinge anerkannten Flüchtlingen, staaten- und schriftenlosen ausländischen Personen, vorläufig Aufgenommenen, Schutzbedürftigen und Asylsuchenden für die Ausreise aus der Schweiz nach den nachfolgenden Bestimmungen Reisepapiere ab. Eine schriftenlose ausländische Person mit Niederlassungsbewilligung hat Anspruch auf einen Pass für eine ausländische Person (Art. 3 Abs. 2 Satz 1 RPAV). Nach Art. 6 Abs. 1 RPAV gilt eine ausländische Person im Sinne dieser Verordnung als schriftenlos, wenn sie keine gültigen heimatlichen Reisepapiere besitzt und ihr nicht zugemutet werden kann, sich bei den zuständigen Behörden ihres Heimat- oder Herkunftsstaates um die Ausstellung oder Verlängerung des Reisepapiers zu bemühen. Das Bundesamt entzieht ein schweizerisches Reisepapier oder ein Reiseersatzdokument unter anderem dann, wenn die ausländische Person die Voraussetzungen zur Ausstellung eines Reisepapiers nicht mehr erfüllt (Art. 13 lit. a RPAV).
b) Streitig ist im vorliegenden Fall, ob der Beschwerdeführer die Voraussetzungen zur Ausstellung eines Reisepapiers erfüllt. Die Vorinstanz hat dies verneint, da der Beschwerdeführer als Inhaber eines gültigen heimatlichen Reisepapiers nicht als schriftenlos im Sinne der einschlägigen Gesetzesbestimmungen gelten könne. Wie die im August 1999 vorgenommenen Abklärungen der Schweizer Botschaft beim Ministerium für auswärtige Angelegenheiten in Sofia ergeben hätten, seien dem Beschwerdeführer von der Bezirksdirektion des Ministeriums für Inneres, Stadt Varna, am 6. Februar 1995 ein bulgarischer Reisepass mit der Seriennummer ...
und am 21. März 1996 ein Personalausweis mit der Seriennummer ... ausgestellt worden. Den vom Beschwerdeführer vorgebrachten Einwand, es müsse sich bei der in der fraglichen Bestätigung der Botschaft bezeichneten Person um einen anderen Mann mit gleichem Namen und Geburtsdatum handeln, sei er doch in Sofia und nicht in Varna geboren, wies die Vorinstanz als unbehelflich zurück, da das fragliche Dokument nicht den Geburts- sondern den Ausstellungsort der darin aufgeführten Dokumente angebe.
c) Der Beschwerdeführer bestreitet, Inhaber des am 6. Februar 1995 ausgestellten bulgarischen Reisepasses mit der Seriennummer ... zu sein. Er macht geltend, dass es sich um eine Namensverwechslung handeln müsse. Weiter trägt er vor, das bulgarische Innenministerium habe ihm erst kurz vor Beschwerdeerhebung wieder bestätigt, dass er keine bulgarische Staatsbürgerschaft mehr besitze.
Der Beschwerdeführer rügt damit sinngemäss eine unvollständige Feststellung des rechtserheblichen Sachverhalts (Art. 104 lit. b OG). Dabei verkennt er jedoch seine eigene Mitwirkungspflicht: Es hätte an ihm gelegen, eine Bestätigung des bulgarischen Innenministeriums einzureichen, dass er auch heute noch nicht die bulgarische Staatsbürgerschaft besitze, oder zumindest seine kürzliche Nachfrage glaubhaft zu machen. Die von ihm eingereichte Bescheinigung des Justizministeriums vom 7. Juli 1993, wonach er von der bulgarischen Staatsbürgerschaft befreit sei, ist jedenfalls nicht geeignet, dies zu belegen, da sie sich auf seinen Status vor sieben Jahren bezieht. Der angerufene Umstand kann daher nicht zu seinen Gunsten gewertet werden.
Gleiches gilt auch für sein Vorbringen, es müsse sich beim fraglichen bulgarischen Pass um eine Namensverwechslung handeln. Es ist nicht zu beanstanden, dass es die Vorinstanz gestützt auf die Abklärungen der Schweizerischen Botschaft in Sofia für erwiesen erachtet hat, dass der Beschwerdeführer Inhaber des bulgarischen Reisepasses mit der Seriennummer ... und des bulgarischen Personalausweises mit der Seriennummer ... sei. Die blosse Behauptung des Beschwerdeführers, der fragliche bulgarische Pass sei an einen Mann in Varna ausgestellt worden, da für ihn ein solcher Pass in Sofia hätte ausgestellt werden müssen, ist nicht geeignet, eine Namensverwechslung zu beweisen oder zumindest glaubhaft zu machen. Aus dem Umstand, dass der Beschwerdeführer auch nach dem 6. Februar 1995, d.h. nach dem Ausstellungsdatum des bulgarischen Reisepass mit der Seriennummer ..., noch in der Schweiz weilt, vermag er entgegen seiner Auffassung nichts zu seinen Gunsten abzuleiten.
Andere Beweismittel bringt der Beschwerdeführer nicht bei. Gegen eine Namensverwechslung spricht im Übrigen auch die Tatsache, dass das Bundesamt bei seiner Anfrage an die Schweizerische Vertretung in Sofia neben (beiden) Vornamen und Geschlechtsnamen sowie Geburtsdatum des Beschwerdeführers auch die Namen der Eltern des Beschwerdeführers angegeben hatte. Es erscheint daher als höchst unwahrscheinlich, wenn nicht sogar ausgeschlossen, dass in Varna eine Person mit identischem Namen, Geburtsdatum und Abstammung existiert. Hinzu kommt, dass der Beschwerdeführer auch nicht in Abrede stellt, den bulgarischen Personalausweis mit der Seriennummer ... zu besitzen. Auf Grund dieser Umstände sowie der bloss allgemeinen, nicht weiter substanziierten Vorbringen in der Beschwerdeschrift besteht für das Bundesgericht kein Anlass, diesbezüglich von Amtes wegen weitere Abklärungen vorzunehmen.
d) Selbst wenn es aber zutreffen würde, dass der Beschwerdeführer über kein heimatliches Reisepapier verfügt, wäre er nicht als schriftenlos im Sinne von Art. 6 Abs. 1 RPAV zu bezeichnen. Wie die Abklärungen der Vorinstanz und des Bundesamtes ergeben haben, steht auf Grund der politischen Veränderungen in Bulgarien ausgebürgerten, ehemals bulgarischen Staatsangehörigen seit geraumer Zeit die Möglichkeit offen, sich wieder einbürgern zu lassen. Da sich die Zumutbarkeit eines solchen Schrittes nicht nach subjektiven, sondern objektiven Massstäben beurteilt, ist nicht ersichtlich, weshalb vom Beschwerdeführer nicht verlangt werden könnte, sich bei den bulgarischen Behörden um ein heimatliches Reisepapier zu bemühen. Fehlt es aber am Erfordernis der Unzumutbarkeit, so ist der Beschwerdeführer nicht als schriftenlos im Sinne von Art. 6 Abs. 1 RPAV zu bezeichnen. Demzufolge sind die Voraussetzungen zur Ausstellung eines Reisepapiers nicht mehr erfüllt und der Pass für Ausländer wurde dem Beschwerdeführer zu Recht entzogen.
e) Die Vorinstanz hat somit weder den rechtserheblichen Sachverhalt unrichtig oder unvollständig festgestellt noch Bundesrecht verletzt.
3.- Die Verwaltungsgerichtsbeschwerde erweist sich daher als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdeführer die Kosten zu tragen (Art. 156 Abs. 1 in Verbindung mit Art. 153 und Art. 153a OG). Eine Parteientschädigung ist nicht geschuldet (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3.- Dieses Urteil wird dem Beschwerdeführer, dem Bundesamt für Flüchtlinge und dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
_
Lausanne, 28. Juli 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Die Gerichtsschreiberin: