Gebühren (konsularischer Schutz), hat sich ergeben: A.- G._ und W.-M._ sind am 3. April 1995 in Sarajevo von serbischen Militärpersonen festgenommen und in der Folge während 34 Tagen festgehalten worden. Sie waren im Rahmen eines Projektes der "Kulturbrücke Schweiz-Sarajevo" seit einer Woche in Sarajevo tätig gewesen. Die Festnahme erfolgte auf dem Weg zum Flughafen mit einem UNPROFOR-Transport an einem Kontrollposten des serbischen Militärs. Das Eidgenössische Departement für auswärtige Angelegenheiten (EDA) und andere Stellen bemühten sich um die Freilassung, welche am 9. Mai 1995 erfolgte. Am 29. Dezember 1995 stellte die Sektion für konsularischen Schutz des EDA G._ und W.-M._ die im Zusammenhang mit ihrer Freilassung entstandenen Kosten von Fr. 7'703. 70 bzw. Fr. 7'792. 50 in Rechnung, wovon ein Anteil von je Fr. 5'670.-- eine damals als "Kaution" bezeichnete Zahlung an die bosnischen Serben für die Freilassung betraf. Am 12. Februar 1996 erliess die Sektion für konsularischen Schutz entsprechende Verfügungen. B.- G._ und W.-M._ erhoben am 13. März 1996 Beschwerde, welche das Eidgenössische Departement für auswärtige Angelegenheiten am 5. Dezember 1996 im Hinblick auf ein parallel geführtes Akteneinsichtsverfahren im Rahmen des Bundesgesetzes über den Datenschutz sistierte. Nach dessen Abschluss durch Urteil des Bundesgerichts vom 19. März 1999 (BGE 125 II 225) wurde die Sistierung am 15. September 1999 wieder aufgehoben. Am 13. Oktober 1999 erliess die Sektion für konsularischen Schutz des EDA wiedererwägungsweise neue Verfügungen und hielt nur noch an der Rückerstattung der geleisteten "Kaution" von je Fr. 5'670.-- für die Freilassung fest. Sie bezog sich hiebei auf zwei Urteile des Bundesgerichts vom 21. Oktober 1996 (s.u.), wonach sich ein Gebühren- bzw. Auslagenerlass rechtfertigen könne, wenn der Aufenthalt im Ausland im Rahmen einer humanitären Mission oder eines anderen Auftrags im allgemeinen Interesse erfolgt sei. Diese Voraussetzung sei hier gegeben, doch sei der Erlass auch der geleisteten "Kaution" nicht angezeigt. Am 6. April 2000 wies das Eidgenössische Departement für auswärtige Angelegenheiten die Beschwerde gegen die Verfügungen vom 12. Februar 1996, soweit nicht gegenstandslos geworden, ab. C.- G._ und W.-M._ haben am 8. Mai 2000 Verwaltungsgerichtsbeschwerde an das Bundesgericht erhoben. Sie beantragen, den angefochtenen Entscheid aufzuheben und das Eidgenössische Departement für auswärtige Angelegenheiten anzuweisen, auf Forderungen ihnen gegenüber, "die dem EDA aufgrund des Entführungsfalles vom 3. April 1995 bis 9. Mai 1995 erwachsen sind", zu verzichten. Das Eidgenössische Departement für auswärtige Angelegenheiten schliesst in seiner Vernehmlassung vom 26. Juni 2000 auf Abweisung der Beschwerde. 