Der im Jahre 1931 geborene österreichische Staatsangehörige V. reiste am 1. Oktober 1980 gemeinsam mit seiner Ehefrau und drei Kindern in die Schweiz ein, um die Geschäftsführung der neugegründeten X. AG, in W., zu übernehmen. Die Fremdenpolizei des Kantons St. Gallen erteilte ihm und seiner Familie am 21. November 1980 die Aufenthaltsbewilligung, die in der Folge wiederholt verlängert wurde. Im Jahre 1987 fiel die X. AG in Konkurs. Danach war V. als Geschäftsführer einer weiteren Gesellschaft tätig. Am 31. Januar 1989 wies die kantonale Fremdenpolizei ein Gesuch um Verlängerung der Aufenthaltsbewilligung ab, im wesentlichen mit der Begründung, der Gesuchsteller habe zu Klagen Anlass gegeben, indem er seinen öffentlichrechtlichen und privat-rechtlichen Verpflichtungen nicht nachgekommen sei, was ständige Betreibungsbegehren zur Folge gehabt habe; auch habe er als Geschäftsführer den Konkurs der X. AG mitverursacht. Dagegen rekurrierte V. an den Regierungsrat des Kantons St. Gallen. Im Rekursverfahren wurde ihm zum Stellenantritt als Geschäftsführer der von ihm neu gegründeten S. AG eine provisorische Aufenthaltsbewilligung erteilt, worauf er den Rekurs gegen die Verfügung vom 31. Januar 1989 zurückzog. Am 15. November 1990 erhielt er wiederum eine ordentliche Aufenthaltsbewilligung, wobei die Fremdenpolizei folgenden Vermerk beifügte:

Mit Urteil der Gerichtskommission Oberrheintal vom 16. April 1991 wurde V. wegen Zweckentfremdung von AHV-Beiträgen, begangen in den Jahren 1983 und 1984, mit Fr. 1'500.-- gebüsst.

Am 20. September 1991 ersuchte V. um Erteilung einer Niederlassungsbewilligung. Die Fremdenpolizei behandelte das Gesuch als solches um Verlängerung der Aufenthaltsbewilligung und wies es mit Verfügung vom 10. November 1992 unter Ansetzung einer Ausreisefrist ab.

Gegen diese Verfügung rekurrierte V. wiederum an den Regierungsrat des Kantons St. Gallen, mit dem Antrag, seinem Gesuch um Verlängerung der Aufenthaltsbewilligung sei stattzugeben. Mit Entscheid vom 18. Januar 1994 wies der Regierungsrat den Rekurs ab. Zur Begründung führte er aus, V. habe die in ihn bei der letzten Verlängerung der Aufenthaltsbewilligung gesetzten Erwartungen nicht erfüllt. So habe er auch in den Jahren 1990 bis 1992 betrieben werden müssen, bis zum Erlass der angefochtenen Verfügung insgesamt 15mal. Die Gesamtbetreibungssumme belaufe sich auf Fr. 370'000.--, wovon nur rund Fr. 9'000.-- bezahlt worden seien. Während des laufenden Rekursverfahrens seien sechs weitere Betreibungen für das Jahr 1992 und zwei für das Jahr 1993 hinzugekommen. Die Gesamtbetreibungssumme habe sich dadurch um mehr als Fr. 100'000.-- vergrössert. Davon seien nur rund Fr. 2'000.-- getilgt worden, während eine Gläubigerin eine Forderung von Fr. 350'000.-- bis Ende 1995 gestundet habe. Gemäss den eigenen Angaben des Rekurrenten verbleibe eine aktuelle Restschuld in der Höhe von ca. Fr. 115'000.--. Das zeige, dass es V. nicht gelungen sei, die Regulierung seiner persönlichen Schulden in den Griff zu bekommen. Zudem sei auch die S. AG, deren sämtliche Arbeitsplätze von Mitgliedern der Familie V. besetzt seien, überschuldet.  Zu berücksichtigen sei ferner, dass auch der ausländische Leumund von V. erheblich getrübt sei. So sei dieser in Deutschland im Jahre 1988 wegen fortgesetzter Umsatzsteuerhinterziehung zu einem Jahr Freiheitsstrafe, ausgesetzt auf vier Jahre Bewährungszeit, sowie im Jahr 1991 wegen Pflichtverletzung bei Zahlungsunfähigkeit in Tatmehrheit mit Vorenthalten von Arbeitsentgelt zu einer Geldstrafe von 90 Tagessätzen verurteilt worden, wobei beide Verurteilungen im Zusammenhang mit seiner Geschäftstätigkeit stünden. Angesichts dieser Umstände überwiege das öffentliche Interesse an seiner Wegweisung das private Interesse am Fortbestand der Aufenthaltsbewilligung.

Gegen den Entscheid des Regierungsrats hat V. am 1. März 1994 Verwaltungsgerichtsbeschwerde an das Bundesgericht erhoben, mit dem Antrag, es sei ihm die Aufenthaltsbewilligung bzw. die Niederlassung zu erteilen.

Der Regierungsrat beantragt, auf die Beschwerde nicht einzutreten, eventuell sie abzuweisen, während das Bundesamt für Ausländerfragen auf Gutheissung und Rückweisung der Sache an die Vorinstanz schliesst.

Das Bundesgericht zieht in Erwägung:

1.- Gemäss Art. 100 lit. b Ziff. 3 OG ist auf dem Gebiete der Fremdenpolizei die Verwaltungsgerichtsbeschwerde unzulässig gegen die Erteilung oder Verweigerung von Bewilligungen, auf die das Bundesrecht keinen Anspruch einräumt. Die zuständigen Behörden entscheiden über die Bewilligung des Aufenthalts im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland nach freiem Ermessen (Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer, ANAG; SR 142.20). Damit steht dem Ausländer grundsätzlich kein Anspruch auf die Erteilung der Aufenthalts- bzw. der Niederlassungsbewilligung zu; die Verwaltungsgerichtsbeschwerde ist deshalb ausgeschlossen, soweit der Ausländer sich nicht auf eine Sondernorm des Bundesrechts oder eines Staatsvertrags berufen kann, die ihm einen Anspruch auf eine solche Bewilligung einräumt. Eine derartige Sondernorm enthält Art. 1 des Abkommens vom 14. September 1950 zwischen dem Schweizerischen Bundesrat und der österreichischen Bundesregierung betreffend zusätzliche Vereinbarungen über die Niederlassungsverhältnisse der beiderseitigen Staatsbürger (SR 0.142.111.631.1). Danach haben österreichische Staatsbürger spätestens nach einem ununterbrochenen, ordnungsgemässen Aufenthalt von zehn Jahren in der Schweiz Anspruch auf Erteilung der Niederlassungsbewilligung. Da der Beschwerdeführer österreichischer Staatsangehöriger ist und sich seit mehr als zehn Jahren ununterbrochen in der Schweiz aufhält, kann er sich somit auf eine staatsvertragliche Vorschrift berufen, die ihm einen Anspruch auf die von ihm beanspruchte Bewilligung einräumt. Ob sämtliche Bewilligungsvoraussetzungen erfüllt sind, ist Frage der materiellen Beurteilung.

2.- a) Nun ist allerdings in der Literatur in Zweifel gezogen worden, ob der Bundesrat befugt sei, ohne Genehmigung durch das Parlament staatsvertraglich Ansprüche auf Niederlassungsbewilligung einzuräumen. Dabei wird insbesondere darauf hingewiesen, dass der Bundesrat mit dem Abschluss solcher Vereinbarungen in die gesetzlich festgelegte Kompetenzverteilung zwischen Bund und Kantonen eingreife und letzteren die Ermessensfreiheit gemäss Art. 4 ANAG nehme, wobei aber das Gesetz keine entsprechende Delegationsnorm zugunsten des Bundesrates enthalte (PETER KOTTUSCH, Die Niederlassungsbewilligung gemäss Art. 6 ANAG, ZBl 87/1986 S. 521 ff.; URBAIN LAMBERCY, La répartition des compétences entre Confédération et cantons en matière de police des étrangers, Diss. Lausanne 1983, S. 222; TONI PFANNER, Die Jahresaufenthaltsbewilligung des erwerbstätigen Ausländers, Diss. St. Gallen 1984, S. 40 f.). Das Bundesgericht seinerseits hat bis heute nicht klar Stellung bezogen. Es hat die Frage offen gelassen, wie weit Staatsverträge, die fremdenpolizeiliche Ansprüche einräumen, der Genehmigung der Bundesversammlung bedürfen, und es hat sich auch nicht dazu geäussert, ob gegebenenfalls kompetenzwidrig eingegangene Verträge vom Richter dennoch anzuwenden sind (vgl. BGE 111 Ib 161 E. 3a S. 166; 100 Ib 226 E. 2 S. 229/30; unveröffentlichtes Urteil R. vom 9. Juli 1993).

b) Nach Art. 102 Ziff. 8 BV wahrt der Bundesrat die Interessen der Eidgenossenschaft nach aussen, wie namentlich ihre völkerrechtlichen Beziehungen, und besorgt die auswärtigen Angelegenheiten überhaupt. "Bündnisse und Verträge mit dem Ausland" fallen jedoch gemäss Art. 85 Ziff. 5 BV "in den Geschäftskreis beider Räte". Das bedeutet nicht, dass die Bundesversammlung bei sämtlichen von der Schweiz eingegangenen Verträgen mitzuwirken und diese zu genehmigen hätte. So fallen Verträge, welche für die Schweiz weder neue Pflichten begründen noch den Verzicht bestehender Rechte zur Folge haben, nicht in den Anwendungsbereich von Art. 85 Ziff. 5 BV (Mitteilung der Direktion für Völkerrecht und des Bundesamtes für Justiz nach zustimmender Kenntnisnahme durch den Bundesrat vom 14. Dezember 1987, in VPB 51/1987 Nr. 58 Ziff. 5 S. 375 ff.; JEAN MONNIER, Les principes et les règles constitutionnels de la politique étrangère suisse, ZSR 105/1986 II S. 221 ff.). Möglich ist sodann auch, dass der Bundesrat durch Landesrecht oder aufgrund eines von der Bundesversammlung genehmigten Staatsvertrags ermächtigt ist, in eigener Kompetenz Verträge abzuschliessen (Mitteilung, a.a.O., Ziff. 6 S. 377 ff.; MONNIER, a.a.O., S. 224 ff.).

Aus dem Ingress des Abkommens vom 14. September 1950 zwischen dem Schweizerischen Bundesrat und der österreichischen Bundesregierung geht hervor, dass diese Vereinbarung "in Anwendung des Staatsvertrages zwischen der Schweiz und der österreichisch-ungarischen Monarchie vom 7. Dezember 1875" ergangen ist, welcher von der Bundesversammlung genehmigt worden war (SR 0.142.111.631). Dieser Niederlassungsvertrag enthält indessen keine Regelung darüber, unter welchen Voraussetzungen eine Niederlassungsbewilligung erteilt wird (vgl. zur beschränkten Tragweite der zum Teil sehr alten Niederlassungsverträge: BGE 119 IV 65 E. 1 S. 67 ff., 111 Ib 169 E. 2 S. 171/72; 110 Ib 63 E. 2a S. 66; 106 Ib 125 E. 2b S. 127/28). Das Abkommen vom 14. September 1950 begründet für die Schweiz folglich neue Pflichten und hat nicht bloss ausführenden Charakter. Der Niederlassungsvertrag enthält aber auch keine Klausel, welche den Bundesrat zum Vertragsabschluss hinsichtlich der Erteilung fremdenpolizeilicher Bewilligungen ermächtigen würde. Im Landesrecht fällt als Grundlage für die alleinige Zuständigkeit des Bundesrates zum Vertragsschluss Art. 25 ANAG in Betracht. Danach ist der Bundesrat unter anderem befugt, die Ein- und Ausreise der Ausländer, die Grenzkontrolle und den kleinen Grenzverkehr zu regeln (Art. 25 Abs. 1 lit. a ANAG). Darin wird zwar keine ausdrückliche, aber doch eine implizite Ermächtigung zum Vertragsschluss erblickt, weil die grenzüberschreitenden Aspekte dieser Verordnungskompetenz praktisch nur mit völkerrechtlicher Regelung erfasst werden können (Mitteilung, a.a.O., S. 379; MONNIER, a.a.O., S. 228). Unter diesem Gesichtspunkt vermag ohne weiteres einzuleuchten, dass etwa Vereinbarungen über die Aufhebung der Visumspflicht vom Bundesrat in eigener Kompetenz abgeschlossen werden dürfen. Die Einräumung von Ansprüchen auf Erteilung einer Niederlassungsbewilligung geht indessen erheblich weiter, und es erscheint zumindest zweifelhaft, ob solches noch von der Befugnis des Bundesrates zur Regelung von Ein- und Ausreise erfasst wird. Es ist indessen entbehrlich, dieser Frage weiter nachzugehen, da - wie nachfolgend zu zeigen ist - der vom Bundesrat abgeschlossene Vertrag für die Schweiz völkerrechtliche Verbindlichkeit erlangt hat und vom Richter anzuwenden ist, selbst wenn die landesrechtliche Kompetenzordnung beim Abschluss nicht respektiert worden sein sollte.

c) Die völkerrechtlichen Regeln über das Vertragsrecht beruhen auf Gewohnheitsrecht, welches in der Wiener Konvention vom 23. Mai 1969 über das Recht der Verträge kodifiziert wurde (VRK; SR 0.111). Für die Schweiz ist diese Konvention, nach Genehmigung durch die Bundesversammlung am 15. Dezember 1989 und Hinterlegung der Beitrittsurkunde am 7. Mai 1990, am 6. Juni 1990 in Kraft getreten. Im vorliegenden Zusammenhang ist vorab Art. 46 VRK von Bedeutung. Danach kann sich ein Staat nicht darauf berufen, dass seine Zustimmung, durch einen Vertrag gebunden zu sein, unter Verletzung einer Bestimmung seines innerstaatlichen Rechts über die Zuständigkeit zum Abschluss von Verträgen ausgedrückt wurde und daher ungültig sei, sofern nicht die Verletzung offenkundig war und eine innerstaatliche Rechtsvorschrift von grundlegender Bedeutung betraf. Von einer offenkundigen Verletzung innerstaatlichen Rechts kann vorliegend nicht die Rede sein, zumal diese Verletzung nicht nur aus schweizerischer, sondern aus der Sicht anderer Staaten objektiv erkennbar sein müsste (vgl. Art. 46 Abs. 2 VRK). Die Schweiz ist demnach durch den vom Bundesrat abgeschlossenen Vertrag völkerrechtlich gebunden. Normen des Völkerrechts sind nun aber, sobald sie für unser Land rechtskräftig werden, fester Bestandteil der schweizerischen Rechtsordnung. Eines besonderen Aktes für die Transformation der völkerrechtlichen Regel in das Landesrecht bedarf es nicht. Das bedeutet gleichzeitig, dass die völkerrechtliche Regel, solange sie für die Schweiz in Kraft ist, von allen Staatsorganen einzuhalten und anzuwenden ist (vgl. dazu die gemeinsame Stellungnahme des Bundesamtes für Justiz und der Direktion für Völkerrecht vom 26. April 1989 über das Verhältnis von Völkerrecht und Landesrecht im Rahmen der schweizerischen Rechtsordnung, in VPB 53/1989 Nr. 54 S. 400 und 403). Auch der Richter kann daher einem Staatsvertrag, der völkerrechtlich verbindlich ist, die Anwendung nicht versagen unter Berufung darauf, dass die innerstaatliche Kompetenzordnung beim Vertragsabschluss nicht eingehalten worden sei. Der vom Bundesrat mit Österreich abgeschlossene Vertrag ist vorliegend anzuwenden, unbesehen darum, ob er der Genehmigung durch die Bundesversammlung bedurft hätte oder nicht.

3.- a) Der Beschwerdeführer kann sich demnach auf einen staatsvertraglichen Anspruch auf Erteilung der Niederlassungsbewilligung berufen, weshalb die Verwaltungsgerichtsbeschwerde grundsätzlich zulässig ist. Im kantonalen Rekursverfahren hatte er freilich nur die Verlängerung der Aufenthaltsbewilligung beantragt, nicht aber die Erteilung der Niederlassungsbewilligung verlangt und auch nicht beanstandet, dass sein Gesuch um Erteilung einer Niederlassungsbewilligung von der kantonalen Fremdenpolizei als ein solches um Verlängerung der Aufenthaltsbewilligung behandelt worden war. Dementsprechend hat der Regierungsrat in seinem Entscheid nur geprüft, ob die Aufenthaltsbewilligung zu verlängern sei. Der Antrag auf Erteilung der Niederlassungsbewilligung hat demzufolge als neu zu gelten. Nun sind aber im Verfahren der Verwaltungsgerichtsbeschwerde neue Begehren grundsätzlich ausgeschlossen (BGE 104 Ib 307 E. 2d S. 314/315; 103 Ib 366 E. 1a S. 368). Indessen könnte dem Beschwerdeführer, falls er aufgrund des Abkommens mit Österreich tatsächlich Anspruch auf Erteilung der Niederlassungsbewilligung hat, was als Rechtsfrage von Amtes wegen zu berücksichtigen ist, die - ein weniger gefestigtes Anwesenheitsrecht gewährende - Aufenthaltsbewilligung erst recht nicht verweigert werden. Unter diesen besonderen Umständen rechtfertigt es sich, trotz der Erweiterung des Rechtsbegehrens auf die Beschwerde einzutreten.

b) Art. 1 des Abkommens vom 14. September 1950 gewährt österreichischen Staatsbürgern nach einem ununterbrochenen und ordnungsgemässen Aufenthalt von zehn Jahren in der Schweiz Anspruch auf Erteilung der Niederlassungsbewilligung. Dass der Beschwerdeführer seit mehr als zehn Jahren ununterbrochenen Aufenthalt in der Schweiz hat, ist bereits festgestellt worden. Ordnungsgemäss ist der Aufenthalt dann, wenn der Ausländer in dieser Zeit über eine Aufenthaltsbewilligung verfügt hat. Auch diese Voraussetzung ist vorliegend erfüllt. In der Rechtsprechung hat das Bundesgericht sodann wiederholt den Eindruck erweckt, zu einem ordnungsgemässen Aufenthalt gehöre zusätzlich auch, dass das persönliche Verhalten des Ausländers zu keinen Beanstandungen Anlass gegeben hat (BGE 116 Ib 113 E. 3 S. 116; 101 Ib 225 E. 3b S. 227/28; 97 I 530 E. 2a S. 534/35). Richtig ist zwar, dass die von der Schweiz im Ausländerrecht eingegangenen Staatsverträge die Anwendung landesrechtlicher Bestimmungen nicht hindern, welche aus Gründen polizeilichen Fehlverhaltens zu einer Bewilligungsverweigerung führen können. Das folgt aber nicht aus dem Erfordernis des ordnungsgemässen Aufenthalts, sondern liegt den Verträgen implizit zugrunde oder ist in anderen Vertragsbestimmungen gar ausdrücklich festgehalten. Art. 5 des hier massgeblichen Abkommens bestimmt, dass die gesetzlichen Vorschriften der beiden Vertragsstaaten über das Erlöschen und den Entzug der Niederlassungsbewilligung (bzw. für Österreich der "Aufenthaltserlaubnis") durch diese Vereinbarung nicht berührt werden. Die Niederlassungsbewilligung erlischt unter anderem, wenn gegen den Ausländer die Ausweisung verfügt wird. Ob dem Beschwerdeführer die Niederlassungsbewilligung zu erteilen oder aber zu verweigern sei, beurteilt sich folglich danach, ob er aus der Schweiz ausgewiesen werden könnte, was wiederum im Lichte der Ausweisungsgründe von Art. 10 ANAG zu beurteilen ist. Nicht massgebend sind dagegen die Gründe, welche nach den Vorschriften des ANAG zu einem Widerruf der Aufenthaltsbewilligung Anlass geben können (Art. 9 Abs. 2 ANAG). Der Beschwerdeführer hat grundsätzlich Anspruch auf Erteilung der Niederlassungsbewilligung; nur ein Verhalten, das die Ausweisung (Art. 10 ANAG) und damit das Erlöschen der Niederlassungsbewilligung (Art. 9 Abs. 3 lit. b ANAG) zur Folge hat, kann die Verweigerung der Bewilligung rechtfertigen.

c) Der Regierungsrat hat im angefochtenen Entscheid lediglich geprüft, ob dem Beschwerdeführer die Aufenthaltsbewilligung unter dem Gesichtswinkel des der kantonalen Behörde nach Art. 4 ANAG zustehenden freien Ermessens zu verlängern sei. Massgebend ist indessen, wie dargelegt, ob die Niederlassungsbewilligung verweigert werden kann, weil gegenüber dem Beschwerdeführer ein Ausweisungsgrund vorliegt. Dabei ist zu beachten, dass die Ausweisung nur zulässig ist, wenn sie nach den gesamten Umständen angemessen erscheint (Art. 11 Abs. 3 ANAG), was eine umfassende Interessenabwägung (vgl. die Kriterien von Art. 16 Abs. 3 ANAV) voraussetzt. Es ist indessen nicht Aufgabe des Bundesgerichts, darüber erstinstanzlich zu entscheiden, zumal das Ergebnis nicht auf der Hand liegt. Vielmehr ist der angefochtene Entscheid aufzuheben und die Sache an den Regierungsrat zurückzuweisen.