Dr. med. dent. R. ist deutscher Staatsangehöriger und Inhaber der deutschen Approbation als Zahnarzt. Er verfügt über eine schweizerische Niederlassungsbewilligung. Seit dem 1. Juli 1992 arbeitet er als Assistent bei Dr. med. dent. M. in Chur. Mit Gesuch vom 3. Oktober 1997 beantragte R. beim Justiz-, Polizei- und Sanitätsdepartement des Kantons Graubünden die Erteilung der Bewilligung zur selbständigen Berufsausübung als Zahnarzt. Das Departement wies das Gesuch am 15. Juni 1998 ab, da R. nicht im Besitz des eidgenössischen Zahnarztdiploms sei. Einen dagegen erhobenen Rekurs wies das Verwaltungsgericht des Kantons Graubünden mit Urteil vom 13. Oktober 1998 ab. Es erwog, gemäss Art. 29 Abs. 2 des kantonalen Gesundheitsgesetzes vom 2. Dezember 1984 werde die Bewilligung zur selbständigen Berufsausübung als Medizinalperson nur Inhabern des eidgenössischen Diploms erteilt. Diese Bestimmung sei weder verfassungs- noch bundesrechtswidrig. Eine Ausnahme sei nach Art. 29 Abs. 3 des Gesundheitsgesetzes nur zulässig, wenn nicht genügend Berufsangehörige mit eidgenössischem Diplom vorhanden seien. Auf dem Platz Chur sei jedoch der zahnärztliche Versorgungsgrad genügend.

R. erhebt staatsrechtliche Beschwerde mit dem Antrag, das Urteil des Verwaltungsgerichts aufzuheben und die Sache zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen. Er rügt eine Verletzung von Art. 4 und 31 BV sowie des Bundesgesetzes vom 6. Oktober 1995 über den Binnenmarkt (Binnenmarktgesetz, BGBM; SR 943.02). Das Bundesgericht weist die Beschwerde ab

aus folgenden Erwägungen:

2.- a) Der Beschwerdeführer rügt eine Verletzung der Handels- und Gewerbefreiheit (Art. 31 BV). Die deutsche Approbation als Zahnarzt sei dem eidgenössischen Diplom gleichwertig. Es sei daher durch kein öffentliches Interesse gerechtfertigt, von ihm zusätzlich noch das eidgenössische Diplom zu verlangen, zumal dieses grund- sätzlich vom Schweizer Bürgerrecht abhängig sei.

b) Unter dem Schutz des Art. 31 BV steht jede gewerbsmässig ausgeübte, privatwirtschaftliche Tätigkeit, die der Erzielung eines Gewinnes oder Erwerbseinkommens dient (BGE 124 I 310 E. 3a S. 313; 123 I 212 E. 3a S. 217; je mit Hinweisen), somit auch die Ausübung des Zahnarztberufs (BGE 117 Ia 90 E. 3b S. 93; Pra 87/1998 Nr. 3 S. 19, E. 1). Art. 31 BV behält jedoch in Abs. 2 kantonale Bestimmungen über die Ausübung von Handel und Gewerben, namentlich im öffentlichen Interesse begründete polizeiliche Massnahmen, vor. Solche Einschränkungen können dem Schutz der öffentlichen Ordnung, der Gesundheit, Sittlichkeit und Sicherheit oder von Treu und Glauben im Geschäftsverkehr dienen (BGE 124 I 310 E. 3a S. 313; 118 Ia 175 E. 1 S. 176 f.; 114 Ia 34 E. 2a S. 36). Unzulässig sind wirtschaftspolitische oder standespolitische Massnahmen, die den freien Wettbewerb behindern, um gewisse Gewerbezweige oder Bewirtschaftungsformen zu sichern oder zu begünstigen. Beschränkungen der Handels- und Gewerbefreiheit bedürfen im Übrigen einer gesetzlichen Grundlage, müssen durch ein überwiegendes öffentliches Interesse gerechtfertigt sein und den Grundsatz der Verhältnismässigkeit sowie der Rechtsgleichheit wahren (BGE 124 I 310 E. 3a S. 313; 123 I 12 E. 2a S. 15, 212 E. 3a S. 217; je mit Hinweisen).

c) Vorliegend besteht - wie der Beschwerdeführer mit Recht nicht bestreitet - in Art. 29 des Gesundheitsgesetzes eine formellgesetzliche Grundlage dafür, dass grundsätzlich nur Medizinalpersonen, die im Besitz des eidgenössischen Diploms sind, eine Bewilligung zur selbständigen Berufsausübung erhalten. Das Bundesgericht hat mit Urteil vom 4. Juli 1997 entschieden, dass die praktisch gleichlautende analoge Regelung des zürcherischen Rechts mit Art. 31 BV vereinbar sei. Es hat erwogen, das eidgenössische Diplom garantiere eine fundierte Ausbildung; das könne zwar bei ausländischen Diplomen ebenfalls zutreffen, doch seien ausländische Ausweise für die schweizerischen Gesundheitsbehörden schwieriger zu beurteilen; das Erfordernis des eidgenössischen Diploms sei auch nicht unverhältnismässig (Pra 87/1998 Nr. 3 S. 19, E. 2b/c). Anders verhält es sich bei medizinischen Hilfsberufen wie Physiotherapeuten, wo das Bundesgericht das Erfordernis eines schweizerischen Diploms als unverhältnismässig beurteilt hat, wenn ein gleichwertiges ausländisches Diplom vorliegt (Urteile vom 9. Juni 1995 i.S. Sch., publiziert in SJ 1995 713, E. 3; vom 16. Oktober 1992 i.S. F., publiziert in RDAT 1993 I n. 27 S. 79, E. 4). Diese Rechtsprechung kann jedoch nicht auf die eidgenössisch geregelten Medizinalberufe übertragen werden (RDAT 1993 I n. 27 S. 79, E. 4c). Erweist sich die gesetzliche Regelung generell als verfassungsmässig, dann hat der Inhaber eines ausländischen Diploms auch keinen Anspruch auf Zulassung, wenn er im Einzelfall die Gleichwertigkeit seines Diploms nachweist. Denn die Überprüfung dieser Gleichwertigkeit ist für die schweizerischen Behörden nicht einfach, und gerade deshalb ist die Beschränkung auf Inhaber des schweizerischen Fähigkeitsausweises zulässig. Dass eine generelle Regelung unter Umständen auch auf Einzelfälle Anwendung findet, in denen der innere Sinn des Gesetzes nicht erfüllt wäre, ist nicht selten und stellt noch keine Unverhältnismässigkeit dar.

d) Gemäss Art. 33 Abs. 2 BV und Art. 1 des Freizügigkeitsgesetzes vom 19. Dezember 1877 (SR 811.11) sind Medizinalpersonen mit eidgenössischem Diplom zur freien Ausübung ihres Berufs im Gebiete der ganzen Eidgenossenschaft befugt. Die Kantone können zusätzlich Inhaber ausländischer Ausweise zulassen, doch sind sie dazu von Bundesrechts wegen nicht verpflichtet (BGE 117 Ia 90 E. 3b S. 94; Pra 87/1998 Nr. 3 S. 19 E. 2b). Daraus, dass einzelne Kantone Inhaber deutscher Zahnarztapprobationen zulassen, kann deshalb der Beschwerdeführer nichts ableiten.

e) Es trifft zu, dass nach Art. 16 der Allgemeinen Medizinalprüfungsverordnung vom 19. November 1980 (AMV; SR 811.112.1) Ausländer nur unter bestimmten Voraussetzungen zur eidgenössischen Medizinalprüfung zugelassen werden, namentlich dann, wenn mit ihrem Heimatstaat Gegenrecht vereinbart wurde. Wenn ein kantonales Gesetz die Zulassung zur selbständigen Berufsausübung vom Besitz des eidgenössischen Diploms abhängig macht, kann es daher im Ergebnis einem Ausländer praktisch verunmöglicht werden, einen Medizinalberuf selbständig auszuüben, selbst wenn er bereit und fachlich in der Lage wäre, das eidgenössische Diplom zu erwerben. Soweit dieses Ergebnis als verfassungswidrig zu bezeichnen sein sollte, wäre dies jedoch nicht die Folge der kantonalen Gesetzgebung, welche das schweizerische Diplom verlangt. Es ergibt sich vielmehr aus der eidgenössischen Medizinalprüfungsverordnung, welche die Zulassung zur eidgenössischen Prüfung grundsätzlich vom Erfordernis der schweizerischen Staatsangehörigkeit abhängig macht, was allenfalls als nicht sachgerecht betrachtet werden könnte (vgl. BGE 123 I 212 E. 3c; 119 Ia 35 E. 4). Ob dieses Erfordernis wirklich verfassungswidrig ist, braucht vorliegend jedoch nicht beurteilt zu werden, da nicht die Zulassung zur eidgenössischen Medizinalprüfung in Frage steht. Im Übrigen ist zu bemerken, dass das Gegenrechtserfordernis für die Zulassung zu bestimmten Berufen im internationalen Verhältnis nicht unüblich ist. Ob allenfalls zukünftig in Kraft tretende internationale Abkommen eine Gegenrechtsvereinbarung mit Deutschland im Sinne von Art. 16 Abs. 1 AMV schaffen werden, steht vorliegend nicht zur Diskussion.

3.- Es fragt sich, ob das seit 1. Juli 1996 in Kraft stehende Binnenmarktgesetz an dieser bisherigen Rechtslage etwas geändert hat.

a) Nach Art. 2 Abs. 1 BGBM hat jede Person das Recht, Waren, Dienstleistungen und Arbeitsleistungen auf dem gesamten Gebiet der Schweiz anzubieten, soweit die Ausübung der betreffenden Erwerbstätigkeit im Kanton oder der Gemeinde ihrer Niederlassung bzw. ihres Sitzes zulässig ist. Der Gesetzgeber wollte damit das im EG-Recht geltende sogenannte Cassis-de-Dijon-Prinzip verankern, wonach ein Produkt, welches den in einem Land geltenden Anforderungen entspricht, auch in anderen Ländern vertrieben werden darf (Vgl. Botschaft zum Binnenmarktgesetz, BBl 1995 I 1213, 1257 1263 f.). Einschränkungen dieses Grundsatzes sind zwar möglich, müssen jedoch die Voraussetzungen von Art. 3 BGBM erfüllen. Art. 2 und 3 BGBM enthalten insoweit eine Präzisierung und Konkretisierung der seit je in Art. 31 BV enthaltenen interkantonalen Komponente der Handels- und Gewerbefreiheit (vgl. BGE 122 I 109 E. 4c/d S. 117 f., mit Hinweisen; THOMAS COTTIER/BENOÎT MERKT, La fonction fédérative de la liberté du commerce et de l'industrie et la loi sur le marché intérieur suisse: l'influence du droit européen et du droit international économique, Festschrift Aubert, Basel 1996, S. 449-471, 459; VINCENT MARTENET/CHRISTOPHE RAPIN, Le marché intérieur suisse, Bern 1999, S. 9; RENÉ RHINOW, Kommentar BV, Rz. 52 ff. zu Art. 31; KILIAN WUNDER, Die Binnenmarktfunktion der schweizerischen Handels- und Gewerbefreiheit im Vergleich zu den Grundfreiheiten in der Europäischen Gemeinschaft, Diss. Basel 1998, S. 124 ff.).

b) Voraussetzung, damit der in Art. 2 BGBM gewährleistete freie Zugang zum Markt überhaupt zum Tragen kommt, ist jedoch, dass die angebotene Ware oder Dienstleistung im Kanton, in welchem die anbietende Person ihren Sitz oder ihre Niederlassung hat, zulässig ist. Das ergibt sich aus dem 2. Halbsatz von Art. 2 Abs. 1 BGBM und wird in Abs. 3 Satz 1 noch verdeutlicht. Das Binnenmarktgesetz regelt die Rechtsstellung von auswärtigen Anbietern im interkantonalen bzw. interkommunalen Verhältnis, nicht aber diejenige der Ortsansässigen (BBl 1995 I 1285). Art. 2 BGBM findet somit keine Anwendung auf kantonalrechtliche Normen, welche die Tätigkeit der innerhalb des Kantons niedergelassenen Personen regeln.

c) Der Beschwerdeführer hat Wohnsitz im Kanton Graubünden und ersucht um die Bewilligung zur Berufsausübung in diesem Kanton. Es handelt sich dabei nicht um ein interkantonales Verhältnis, das in den Geltungsbereich von Art. 2 BGBM fällt. Die Zulässigkeit seiner Berufsausübung richtet sich gemäss Art. 2 Abs. 3 BGBM - innert der Schranken der Verfassung - einzig nach bündnerischem Recht. Insoweit hat das Binnenmarktgesetz - unter Vorbehalt von seinem Art. 4 - gegenüber der bisherigen Rechtslage keine Änderung zur Folge.

d) Nach Art. 4 Abs. 1 BGBM gelten kantonale oder kantonal anerkannte Fähigkeitsausweise zur Ausübung einer Erwerbstätigkeit auf dem gesamten Gebiet der Schweiz, sofern sie nicht einer Einschränkung nach Art. 3 BGBM unterliegen. Anders als Art. 2 BGBM beschränkt sich dies nicht auf das Anbieten von Waren, Dienst- und Arbeitsleistungen, sondern gilt auch für die Niederlassung. Art. 4 BGBM erweitert damit den Anwendungsbereich des Herkunftsprinzips auf die Niederlassung, soweit diese von einem Fähigkeitsausweis abhängig ist.

e) Der Beschwerdeführer bringt vor, verschiedene schweizerische Kantone anerkennten das deutsche Diplom als mit dem schweizerischen gleichwertig. Es fragt sich, ob Art. 4 BGBM auch gilt für ausländische Ausweise, die von einzelnen Kantonen anerkannt werden.

Der Vorentwurf zum Binnenmarktgesetz hatte die Formulierung «in der Schweiz erworbene» Fähigkeitsausweise enthalten (BBl 1995 I 1213, 1256). Da dies zur irrtümlichen Annahme verleiten konnte, es seien auch private Fähigkeitsausweise gemeint, ersetzte der Entwurf diese Formulierung durch den Ausdruck «kantonale oder kantonal anerkannte», um klarzustellen, dass das Gesetz nur öffentlichrechtliche Vorschriften bezüglich der Anerkennung von Fähigkeitsausweisen erfasst, nicht aber irgendwelche private Diplome (Amtl. Bull. 1995 S 875 [Berichterstatterin Simmen]); eine materielle Änderung gegenüber dem Vorentwurf war damit nicht beabsichtigt (BBl 1995 I 1256). Weiterhin sollten nur die in der Schweiz erworbenen Fähigkeitsausweise anerkannt werden (BBl 1995 I 1266 f.; vgl. auch KARL WEBER, Das neue Binnenmarktgesetz, Schweizerische Zeitschrift für Wirtschaftsrecht 1996 S. 164-176, 168). Daraus ergibt sich, dass Art. 4 BGBM nach der Absicht des Gesetzgebers auf schweizerische Fähigkeitsausweise beschränkt ist. Die Kantone sind nicht verpflichtet, ein bloss von einzelnen Kantonen anerkanntes ausländisches Diplom gestützt auf Art. 4 BGBM anzuerkennen. Der Beschwerdeführer kann sich daher nicht auf diese Bestimmung berufen.

4.- a) Der Beschwerdeführer rügt eine Verletzung von Treu und Glauben (Art. 4 BV). Das kantonale Justiz-, Polizei- und Sanitätsdepartement hatte am 12. Februar 1997 mit einem Schreiben an den Bündner Ärzteverein, den Bündnerischen Apotheker-Verein und die Graubündnerische Zahnärzte-Gesellschaft eine «Praxisänderung» angekündigt: Es hatte erwogen, gestützt auf BGE 119 Ia 35 sowie Art. 2 und 3 BGBM könne einem niedergelassenen Ausländer die Zulassung zur selbständigen Berufsausübung als Medizinalperson nicht verwehrt werden, wenn sein ausländisches Diplom dem eidgenössischen gleichwertig sei. Daher werde künftig den ausländischen Medizinalpersonen, die im Besitze der Niederlassungsbewilligung und eines dem eidgenössischen gleichwertigen ausländischen Diploms seien, die Bewilligung zur selbständigen Berufsausübung erteilt werden, sofern keine Verweigerungs- oder Entzugsgründe im Sinne von Art. 31 des Gesundheitsgesetzes vorlägen. Der Beschwerdeführer bringt vor, gestützt auf diese «Praxisänderung», die als Feststellungsentscheid zu qualifizieren sei, habe er sein Gesuch gestellt und im Vertrauen darauf verschiedene persönliche Dispositionen getroffen. Es verstosse gegen Treu und Glauben, wenn die Behörden nun davon wieder abwichen.

b) Die rechtsanwendenden Behörden sind auf Grund des Legalitätsprinzips an das Gesetz gebunden. Vom Gesetz kann nur abgewichen werden, wenn dieses höherrangigem Recht widerspricht. Die Nichtanwendung eines Gesetzes mit der unzutreffenden Begründung, dieses sei verfassungs- oder bundesrechtswidrig, ist jedoch willkürlich (BGE 119 Ia 433 E. 4 S. 439 ff.; 111 Ia 176 E. 3c S. 178 f.). Das Departement hatte in seinem Schreiben von 12. Februar 1997 die Regelung von Art. 29 des Gesundheitsgesetzes als verfassungswidrig beurteilt, insbesondere mit Hinweis auf BGE 119 Ia 35. Dieser Entscheid betraf jedoch die Frage, ob die Zulassung zu einer Anwaltsprüfung vom schweizerischen Bürgerrecht abhängig gemacht werden könne. Das ist eine andere Frage als die hier zur Diskussion stehende, ob für die Zulassung zur Berufsausübung ein schweizerischer Fähigkeitsausweis verlangt werden könne. Auch in BGE 119 Ia 35 wurde nicht in Frage gestellt, dass die Zulassung als Anwalt vom Bestehen einer schweizerischen Anwaltsprüfung abhängig gemacht werden kann. Die Erwägungen im Schreiben des Departements vom 12. Februar 1997 waren insoweit unzutreffend. Sodann hat das Bundesgericht nach diesem Schreiben im zitierten Urteil vom 4. Juli 1997 klargestellt, dass derartige Regelungen, wie sie auch in Art. 29 des bündnerischen Gesundheitsgesetzes enthalten sind, der Verfassung nicht widersprechen. Nach dem vorne Ausgeführten widerspricht diese Bestimmung auch nicht dem Binnenmarktgesetz. Unter diesen Umständen war das Departement gehalten, von seiner unzutreffenden Auffassung abzuweichen und das Gesetz anzuwenden.

c) Eine Abweichung vom Gesetz kommt unter diesen Umständen nur nach den Regeln des Vertrauensschutzes in Frage, wenn der Beschwerdeführer sich nach Treu und Glauben auf behördliche Zusicherungen verlassen konnte und gestützt darauf entsprechende Dispositionen getroffen hat. Voraussetzung dafür ist jedoch, dass sich das Verhalten der Behörde auf eine konkrete, den betreffenden Bürger berührende Angelegenheit bezieht (BGE 122 II 113 E. 3b/cc S. 123, mit Hinweisen). Das Schreiben des Departements vom 12. Februar 1997 würde diese Voraussetzung selbst dann nicht erfüllen, wenn es - wie der Beschwerdeführer vorbringt und was übrigens als fraglich erscheint - als Allgemeinverfügung zu qualifizieren wäre. Es handelte sich dabei um eine generelle Ansichtsäusserung des Departementsvorstehers, die weder an den Beschwerdeführer adressiert war noch dessen konkrete Situation betraf. Die Verbindlichkeit behördlicher Äusserungen auch auf derartige allgemeine Verlautbarungen auszudehnen, hätte zur Folge, dass in einem weiten Umfang das objektive Recht zur Disposition der rechtsanwendenden Behörden gestellt würde, indem diese durch gesetzlich nicht abgedeckte Meinungsäusserungen einem breiten Publikum die Berufung auf eine gesetzwidrige Praxis ermöglichen könnten. Damit würden die Rechtssicherheit und das demokratische Prinzip des Gesetzesvorrangs in einem untragbaren Ausmass tangiert.

5.- Der Beschwerdeführer rügt schliesslich eine Verletzung von Art. 4 Abs. 2 BGBM, indem sowohl das Departement als auch das Verwaltungsgericht ihm entgegen dieser Bestimmung Verfahrenskosten auferlegt hätten.

Nach Art. 4 Abs. 2 BGBM hat die betroffene Person bei Beschränkungen nach Art. 3 BGBM Anspruch darauf, dass in einem einfachen, raschen und kostenlosen Verfahren geprüft wird, ob ihr aufgrund ihres Fähigkeitsausweises der freie Zugang zum Markt zu gewähren ist oder nicht. Diese Vorschrift gilt für das Bewilligungsverfahren schlechthin (BGE 125 II 56 E. 5b S. 63 f.). Sie gilt nicht nur, wenn es im kantonalen Verfahren um die beruflichen Fähigkeiten des Gesuchstellers im engeren Sinne geht, sondern auch dann, wenn der Fähigkeitsausweis zwar anerkannt, der freie Zugang zum Markt aber aus anderen Gründen beschränkt wird (BGE 123 I 313 E. 5 S. 323). Wie sich aus dem Bisherigen ergibt, geht es vorliegend jedoch gar nicht um die Frage, ob der nach Binnenmarktgesetz gewährleistete Zugang zum Markt beschränkt wird. Vielmehr ist das Binnenmarktgesetz auf den vorliegenden Sachverhalt gar nicht anwendbar. Die in Art. 4 Abs. 2 vorgesehene Kostenlosigkeit auch auf derartige Fälle auszudehnen, hätte zur Folge, dass jede Rechtsstreitigkeit, die in irgendeiner Weise ein kantonalrechtliches Hindernis für die Ausübung einer privatwirtschaftlichen Tätigkeit zum Thema hat, in einem kostenlosen Verfahren entschieden werden müsste. Damit würde der im Verwaltungs- und Verwaltungsjustizverfahren übliche Grundsatz, dass der Verursacher einer Verwaltungshandlung bzw. der im Verwaltungsjustizverfahren Unterlegene die Kosten zu tragen hat, für einen wesentlichen Teil des gesamten Verwaltungsrechts aufgehoben. Ein derart weitreichender Eingriff in die Finanz- und Verfahrensautonomie der Kantone kann dem Binnenmarktgesetz nicht entnommen werden.