Das Bundesgericht zieht in Erwägung:
1.
X._ ist mazedonischer Staatsangehöriger. Er wurde im Jahr 2002 in Appenzell Ausserrhoden beim kantonal approbierten Zahnarzt A._ als Zahntechniker angestellt. Auf dessen Gesuch hin wurde er am 14. November 2005 vom Departement Gesundheit zur Ausbildung zum kantonal approbierten Zahnarzt zugelassen. Zwischen dem 10. Februar 2006 und dem 19. Juni 2008 bestand er drei Prüfungen mit Erfolg. Hingegen war er bei einem Teil der mündlichen Schlussprüfung nicht erfolgreich. Am 6. Mai 2009 teilte ihm das Departement Gesundheit mit, dass das neue Gesundheitsgesetz den Beruf des kantonal approbierten Zahnarztes seit dem 1. Januar 2008 nicht mehr vorsehe. Das Departement verlangte am 22. Oktober 2009 von A._ ein Gesuch für eine Anstellung von X._ als Assistent sowie die Immatrikulationsbescheinigung einer anerkannten Universität für Zahnmedizin. Am 28. Oktober 2009 stellte A._ ein solches Gesuch um Arbeitsbewilligung für X._ als Assistent. Gleichzeitig sandte er eine Beglaubigung der Medizinischen Universität Sofia vom 1. September 2009, wonach X._ seit September 2004 als ordentlicher Student im Fachbereich Zahnmedizin immatrikuliert sei. Dies bestätigte X._ anlässlich einer Besprechung am 30. November 2009 im Departement Gesundheit ausdrücklich. Abklärungen beim Konsulat der Republik Bulgarien ergaben indessen, dass er nie als Student an der Fakultät für Dentalmedizin in Sofia eingeschrieben und die Bestätigung gefälscht war. Ein von ihm im Dezember 2010 bei den Strafbehörden eingereichtes Diplom der Medizinischen Universität Sofia erwies sich ebenfalls als nicht authentisch.
Der Einzelrichter des Kantonsgerichts von Appenzell Ausserrhoden verurteilte X._ am 15. Januar 2013 wegen Fälschung von Ausweisen im Sinne von <ref-law> (sowie wegen einfacher Verletzung der Verkehrsregeln) zu einer Geldstrafe von 90 Tagessätzen zu Fr. 100.--, bedingt aufgeschoben bei einer Probezeit von zwei Jahren, sowie einer Busse von Fr. 600.-- bzw. einer Ersatzfreiheitsstrafe von sechs Tagen. Das Obergericht von Appenzell Ausserrhoden wies am 29. Oktober 2013 eine Berufung von X._ ab.
X._ beantragt beim Bundesgericht, das Urteil vom 29. Oktober 2013 sei aufzuheben und er in Sachen Fälschung von Ausweisen freizusprechen. Die einfache Verletzung der Verkehrsregeln werde anerkannt, und eine entsprechende Busse sei bereits bezahlt worden.
2.
Im vorliegenden Verfahren ist nur zu prüfen, ob der Beschwerdeführer den Tatbestand von <ref-law> erfüllt hat oder nicht. Soweit seine Vorbringen für diese Frage irrelevant sind, sind sie unzulässig. So ist es z.B. ohne Belang, ob die Prüfungen für den kantonal approbierten Zahnarzt von einer Kommission abgenommen wurden, die "ohne gesetzliche Grundlage" gehandelt haben soll (Beschwerde S. 3). Im Folgenden beschränkt sich das Bundesgericht auf die für das Ergebnis entscheidenden Fragen.
3.
Die Beweiswürdigung und die darauf beruhenden tatsächlichen Feststellungen der Vorinstanz können vor Bundesgericht angefochten werden, wenn sie offensichtlich unrichtig im Sinne von <ref-law> bzw. willkürlich im Sinne von <ref-law> sind. Willkür liegt vor, wenn der angefochtene Entscheid im bemängelten Punkt offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Dass eine andere Lösung ebenfalls möglich oder sogar etwas wahrscheinlicher ist, genügt nicht (<ref-ruling> E. 6.1, 137 I 1 E. 2.4). Die angebliche Willkür ist in der Beschwerde präzise zu rügen, und die Rüge ist zu begründen (<ref-law>).
Soweit die Vorbringen des Beschwerdeführers den Anforderungen nicht genügen, sind sie nicht zu hören. Dies betrifft z.B. seine Behauptung, bei den von ihm eingereichten Dokumenten handle es sich keineswegs um Fälschungen, sondern sie seien von der Universität Sofia ausgestellt worden (Beschwerde S. 8). Woraus sich das ergeben soll, sagt er nicht.
4.
In tatsächlicher Hinsicht stellt die Vorinstanz fest, der Beschwerdeführer habe bereits im Jahr 2003 gewusst, dass es irgendwann keine neuen Bewilligungen als kantonal approbierter Zahnarzt mehr geben werde (Urteil S. 8). Der Beschwerdeführer rügt diese Erwägung als unrichtig (Beschwerde S. 6). Er legt indessen nicht dar, inwieweit sie offensichtlich unrichtig im Sinne von <ref-law> bzw. willkürlich im Sinne von <ref-law> sein soll. Die Vorinstanz stützt sich auf eine Notiz über die Besprechung vom 30. November 2009. Danach behauptete der Beschwerdeführer bei dieser Besprechung, er habe sich im September 2004 an der Medizinischen Universität Sofia für das Studienfach Zahnmedizin immatrikuliert, da er bereits im Jahre 2003 darüber informiert worden sei, dass es irgendwann keine neuen Bewilligungen mehr als kantonal approbierter Zahnarzt geben werde. Eigentlich habe er in Zürich studieren wollen, wo aber strengere Anwesenheitspflichten gelten, so dass er nicht hätte Vollzeit arbeiten und gleichzeitig studieren können (KA act. 11/2/5 S. 1). Wenn die Vorinstanz auf diese Notiz abstellte, war das offensichtlich nicht willkürlich.
5.
Tatobjekte von <ref-law> sind Ausweisschriften, Zeugnisse oder Bescheinigungen. Unter diese Objekte fällt nach der Rechtsprechung z.B. eine Bescheinigung, in welcher eine Universität den Doktortitel anerkennt, den eine andere Universität verliehen hat, weil die Bescheinigung den Zugang zu weiterführenden Studien, Examina und Berufen ermöglicht oder erleichtert (<ref-ruling> E. 1). Dasselbe gilt im vorliegenden Fall. Die Universität Sofia bescheinigte angeblich, dass der Beschwerdeführer bei ihr immatrikuliert sei und dort auch studiere (KA act. 11/2/4). Genau diese Bescheinigung war Voraussetzung dafür, dass das Departement Gesundheit eine Tätigkeit als Assistent bei A._ bewilligen konnte. Folglich war sie bestimmt und geeignet, eine Tatsache von rechtlicher Bedeutung zu beweisen. Dass sie für den Beschwerdeführer nach seinem subjektiven Empfinden "keine rechtliche Wirkung" hatte (Beschwerde S. 7), ist unerheblich.
6.
Strafbar nach <ref-law> macht sich unter anderem, wer ein Tatobjekt zur Täuschung gebraucht. Indem der Beschwerdeführer die gefälschte Bescheinigung der Universität Sofia durch A._ beim Departement Gesundheit einreichen liess, hat er klarerweise eine Tathandlung begangen.
7.
In subjektiver Hinsicht verlangt <ref-law> neben Vorsatz die Absicht, sich (oder einem anderen) das Fortkommen zu erleichtern. Auch diese Voraussetzung ist erfüllt, ging es dem Beschwerdeführer nach den Feststellungen der Vorinstanz doch darum, eine Bewilligung für eine Tätigkeit als Assistent bei A._ zu erhalten. Er wollte sich somit das Leben erleichtern, was ausreicht (Urteil 6B_619/2012 vom 18. Dezember 2012, E. 1.2 mit Hinweis).
8.
Die Beschwerde ist im Verfahren nach <ref-law> abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Obergericht von Appenzell A.Rh., 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 28. April 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Monn