Sachverhalt: A. A.a. A._ absolvierte nach dem (bis Ende 2007 in Kraft gestandenen) Gesetz [des Kantons Appenzell Ausserrhoden] vom 25. April 1965 über das Gesundheitswesen (aGG/AR) eine Ausbildung zum kantonal approbierten Zahnarzt. Am 1. Januar 2008 trat das revidierte Gesundheitsgesetz [des Kantons Appenzell Ausserrhoden] vom 25. November 2007 (GG/AR; bGS 811.1) in Kraft, womit der Berufsstand der kantonal approbierten Zahnärzte abgeschafft und insbesondere auch das entsprechende Prüfungsreglement für kantonal approbierte Zahnärzte ersatzlos aufgehoben wurde. A._ hatte Ende 2007 die Prüfungen zum kantonal approbierten Zahnarzt noch nicht alle absolviert bzw. nur teilweise bestanden und war somit (noch) nicht Inhaber einer altrechtlichen Berufsausübungsbewilligung als kantonal approbierter Zahnarzt. A.b. Das Amt für Gesundheit des Kantons Appenzell Ausserrhoden führte auch nach Inkrafttreten des revidierten GG/AR bzw. der Aufhebung des Reglements noch zwei Prüfungen mit A._ durch (am 19. Juni 2008: Wiederholung der schriftlichen Pharmakologie-Prüfung bzw. am 11. Dezember 2008: erster Teil der mündlichen Schlussprüfung). Nachdem er die letztere nicht bestanden hatte, teilte ihm die Prüfungskommission am 12. Dezember 2008 mit, dass er die Prüfung nur einmal wiederholen könne und sich dazu beim Departement anmelden müsse. Mit Schreiben vom 6. Mai 2009 teilte das Departement Gesundheit A._ jedoch mit, dass er seine Ausbildung zum kantonal approbierten Zahnarzt aufgrund der neuen Rechtslage nicht mehr abschliessen könne. Dazu fehle die gesetzliche Grundlage, zumal der Gesetzgeber keine Übergangsfrist für Personen, die sich im laufenden Prüfungsverfahren befanden, vorgesehen habe. A.c. A._ arbeitete in der Folge als Assistent und gab an, ein Studium der Zahnmedizin an einer bulgarischen Universität zu absolvieren. Da sich die eingereichte Immatrikulationsbestätigung an der Universität als gefälscht erwies, untersagte das Departement Gesundheit mit Verfügung vom 10. Dezember 2009 A._ jegliche zahnärztliche Tätigkeit mangels eines Ausbildungsnachweises. Diese Verfügung erwuchs unangefochten in Rechtskraft. Mit Urteil 6B_317/ 2014 vom 28. April 2014 bestätigte das Bundesgericht schliesslich eine Verurteilung von A._ durch das Obergericht des Kantons Appenzell Ausserrhoden wegen Fälschung des oben erwähnten (Ausbildungs-) Ausweises im Sinne von Art. 252 StGB. B. Am 3. Juni 2013 stellte A._ beim Amt für Gesundheit das Gesuch, als kantonal approbierter Zahnarzt nach altem Recht zur Abschlussprüfung und dann als kantonal approbierter Zahnarzt zur Berufsausübung zugelassen zu werden. Am 25. Juli 2013 wies das Amt das Gesuch ab. Den dagegen von A._ erhobenen Rekurs wies das Departement Gesundheit mit Entscheid vom 17. Januar 2014 ab. Am 27. Mai 2015 wies das Obergericht des Kantons Appenzell Ausserrhoden, 4. Abteilung, die dagegen erhobene Beschwerde ab, soweit es darauf eintrat. C. Mit Eingabe vom 22. Januar 2016 erhebt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, das angefochtene Urteil vom 27. Mai 2015 sei aufzuheben und ihm sei die Möglichkeit einzuräumen, den Beruf als kantonal approbierter Zahnarzt altrechtlich zu erlangen. Weiter sei ihm die zahnärztliche Tätigkeit wieder zu erlauben und die Verfügung des Amtes für Gesundheit vom 10. Dezember 2009 sei aufzuheben. Eventualiter sei die "geforderte Schadenersatzsumme" vom Kanton zu bezahlen und die bulgarische Urkunde sei nicht Gegenstand der Beschwerde. Das Departement für Gesundheit und Soziales des Kantons Appenzell Ausserrhoden beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei die Beschwerde abzuweisen. Das Obergericht des Kantons Appenzell Ausserrhoden beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne.