Sachverhalt: A. Mit Urteil des Kreisgerichts St. Gallen vom 8. Dezember 2005 wurde die Ehe von A.A._ und E.A._ geschieden. A.A._ wurde gestützt auf eine Vereinbarung mit seiner Ehefrau vom 23. November 2005 verpflichtet, seinen Töchtern B.A._ (geb. 17. April 1989), C.A._ (geb. 18. Mai 1990), D.A._ (geb. 4. November 1991) und F.A._ (geb. 11. Februar 1995) einen indexierten Unterhalt in der Höhe von Fr. 2'500.-- pro Monat und Kind (zuzüglich allfälliger Kinderzulagen) bis zum ordentlichen Abschluss einer Erstausbildung zu bezahlen. B. B.a. Mit Vermittlungsbegehren vom 29. Januar 2013 leitete A.A._ beim Kantonsgericht Appenzell Ausserrhoden gegen seine Töchter B.A._, C.A._ und D.A._ ein Verfahren auf Abänderung des Scheidungsurteils ein. Er verlangte, den Unterhalt mit Wirkung ab 31. Januar 2013 auf höchstens Fr. 1'250.-- je Kind herabzusetzen, längstens zahlbar bis zum ordentlichen Abschluss der Erstausbildung des jeweiligen Kindes. B.b. Mit Entscheid vom 9. Juli 2014 wies die Einzelrichterin des Kantonsgerichts die Abänderungsklage ab und auferlegte A.A._ die Verfahrens- und Parteikosten. B.c. A.A._ wandte sich in der Folge erfolglos an das Obergericht des Kantons Appenzell Ausserrhoden. Mit Entscheid vom 16. Juni 2015 wies der Einzelrichter des Obergerichts die Berufung ab (Disp. Ziff. 1). Die Kosten des Verfahrens vor der Einzelrichterin des Kantonsgerichts wurden bestätigt (Disp. Ziff. 3). Für das Berufungsverfahren wurde A.A._ eine Gerichtsgebühr von Fr. 6'000.-- auferlegt (Disp. Ziff. 4). Zudem wurde er verpflichtet, seinen Töchtern eine Parteientschädigung von Fr. 20'586.75 zu bezahlen (Disp. Ziff. 6). Eine von den Töchtern erhobene Anschlussberufung wurde im selben Urteil ebenfalls unter Kosten- und Entschädigungsfolge abgewiesen (Disp. Ziff. 2, 5 und 7). C. Bezüglich der zum damaligen Zeitpunkt noch nicht volljährigen Tochter F.A._ strengte A.A._ ein separates, gegen seine frühere Ehefrau E.A._ gerichtetes Verfahren an. Dieses mündete in einen Entscheid des Kreisgerichts St. Gallen betreffend Abänderung des Scheidungsurteils vom 4. November 2014. Der Unterhalt für die jüngste Tochter bildet demnach nicht Gegenstand dieses Verfahrens. D. D.a. Mit Beschwerde in Zivilsachen vom 20. August 2015 wendet sich A.A._ an das Bundesgericht. Er verlangt, Ziff. 1, 3, 4 und 6 des Entscheids des Obergerichts aufzuheben und die von ihm geschuldeten monatlichen Unterhaltsbeiträge mit Wirkung ab 31. Januar 2013 auf höchstens Fr. 1'250.-- je Kind herabzusetzen, längstens zahlbar bis zum ordentlichen Abschluss der Erstausbildung des jeweiligen Kindes. Eventualiter sei die Angelegenheit an die Vorinstanz zurückzuweisen, damit diese nach weiteren Abklärungen neu entscheide. Alles unter Kosten- und Entschädigungsfolgen zulasten der Töchter für die vorinstanzlichen Verfahren vor dem Kantons- und dem Obergericht Appenzell Ausserrhoden sowie für das bundesgerichtliche Verfahren. D.b. B.A._, C.A._ und D.A._ (Beschwerdegegnerinnen) beantragen in ihrer Vernehmlassung vom 29. Februar 2016, die Beschwerde abzuweisen. Ferner weisen sie darauf hin, dass die Belastung für den Beschwerdeführer seit dem Sommer 2015 geringer geworden sei, nachdem er im Juli 2015 zum letzten Mal Alimente für B.A._ und C.A._ habe bezahlen müssen. Im Sommer 2017 werde voraussichtlich auch D.A._ ihr Studium beendigen. Das Obergericht hat auf die Ausführungen im angefochtenen Entscheid verwiesen und auf eine Vernehmlassung verzichtet (Eingabe vom 2. Februar 2016). D.c. Der Beschwerdeführer nahm am 8. März 2016 zur Vernehmlassung der Töchter Stellung und hielt an seinen Begehren fest. Die Eingabe wurden den Beschwerdegegnerinnen zur Wahrung des rechtlichen Gehörs zugestellt.