Punktespielautomaten, Abräumefrist, hat sich ergeben:
A.- In den Jahren 1995/1996 erliess das Eidgenössische Justiz- und Polizeidepartement (EJPD) acht verschiedene Verfügungen, wonach die Spielautomaten Lucky Fun, Treble Chance Fun, Reel Poker Fun, Tropical Dream Plus, Super Cherry 600, Red Hot Seven Fun, Cup Final und Super Ciliege Amusement nicht unter die damalige eidgenössische Spielbankengesetzgebung (altes Spielbankengesetz vom 5. Oktober 1929; BS 10 280) fielen. Mit acht im Wesentlichen gleich lautenden Verfügungen vom 21. Dezember 1999 widerrief das EJPD diese Verfügungen und legte fest, dass die bereits im Betrieb stehenden Automaten noch bis zum 31. März 2000 betrieben werden dürfen. Eine dagegen erhobene Verwaltungsgerichtsbeschwerde wurde vom Bundesgericht mit Urteil vom 7. Juli 2000 teilweise gutgeheissen; das Bundesgericht stellte fest, dass die genannten Spielautomaten Geldspielautomaten im Sinne des inzwischen in Kraft getretenen Bundesgesetzes vom 18. Dezember 1998 über Glücksspiele und Spielbanken (Spielbankengesetz, SBG; SR 935. 52) seien und der Übergangsbestimmung von <ref-law> unterstünden. Im Übrigen wies es die Beschwerde ab.
B.- Am 28. September 2000 richtete das Volkswirtschaftsdepartement des Kantons St. Gallen ein Schreiben an alle politischen Gemeinden des Kantons. Darin führte es nach einleitenden Bemerkungen aus:
"Das Bundesgericht hat vor kurzem entschieden,
dass die gängigen Punktespielautomaten als Geldspielautomaten
im Sinne des eidgenössischen Spielbankengesetzes
zu qualifizieren sind. Es ist daher
verboten, sie ausserhalb von konzessionierten
Spielbanken aufzustellen. Im Kanton St. Gallen gilt
dieses Verbot per sofort, weil das kantonale Recht
keinen Raum für Übergangsregelungen bietet. Die
Regierung begrüsst diese eindeutige Rechtslage,
weil sie im Hinblick auf die Errichtung von konzessionierten
Spielbanken klare Verhältnisse
schafft.
Es gilt somit allen Betroffenen zur Kenntnis
zu bringen, dass die Punktespielautomaten des Typs
Super Cherry 600, Treble Chance Fun, Lucky Fun,
Super Ciliege Amusement, Tropical Dream Plus, Red
Hot 7 Fun, Reel Poker Fun und Cup Final im Kanton
ausserhalb von konzessionierten Spielbanken nicht
mehr aufgestellt werden dürfen. Das Verbot gilt per
sofort, soll aber zur Wahrung der Verhältnismässigkeit
ab 1. Dezember 2000 durchgesetzt werden. Wir
ersuchen Sie als Bewilligungs- und Aufsichtsinstanz
gemäss Art. 2 des kantonalen Gesetzes über Spielgeräte
und Spiellokale (sGS 554. 3), zusammen mit
den Polizeiorganen eine Bestandesaufnahme vorzunehmen
und den Betreibern der entsprechenden Geräte
eine Kopie dieses Schreibens abzugeben. Ab 1. Dezember
2000 werden die Strafverfolgungsbehörden
aufgrund entsprechender Anzeigen aktiv. Gemäss dem
kantonalen Gesetz über Spielgeräte und Spiellokale
wird mit Busse bestraft, wer an verbotenen Spielgeräten
spielen lässt. Gemäss dem eidgenössischen
Spielbankengesetz wird mit Haft oder Busse bis
Fr. 500'000.--- bestraft, wer Glücksspiele ausserhalb
konzessionierter Spielbanken organisiert oder
gewerbsmässig betreibt.. "
Eine Kopie des Schreibens wurde ausserdem der Kantonspolizei, der Staatsanwaltschaft, der Staatskanzlei, dem Kantonalverband für Hotellerie und Restauration (zuhanden der Mitglieder), den vom erwähnten Bundesgerichtsentscheid betroffenen Automatenherstellern sowie dem EJPD zur Kenntnis zugestellt.
C.- Am 23. Oktober 2000 gelangte die Firma D._ an das Volkswirtschaftsdepartement des Kantons St. Gallen und beantragte, dass die genannten Geräte erst ab 1. April 2001 nicht mehr aufgestellt werden dürfen. Für den Fall, dass das Departement diesem Antrag nicht stattgebe, wurde um Erlass einer anfechtbaren Verfügung ersucht. Mit Schreiben vom 6. November 2000 teilte das Departement der Firma D._ mit, es könne auf das Gesuch nicht eintreten, da Geldspielautomaten ausserhalb konzessionierter Spielbanken generell nicht zulässig seien, das Departement nicht berechtigt sei, Ausnahmebewilligungen zu erteilen und auch kein Raum für eine übergangsrechtliche Ausnahmebewilligung bestehe. Das Schreiben vom 28. September 2000 habe keine neue Rechtslage geschaffen, sondern nur eine Mitteilung enthalten, welche es den Gemeinden erleichtern sollte, das geltende Verbot künftig durchzusetzen.
D.- Am 20. November 2000 erhoben die A._ GmbH, die B._ AG, die C._ AG und die D._ betreffend die "Verfügung des Volkswirtschaftsdepartements des Kts. St. Gallen vom 6. Oktober 2000" Rekurs an die Regierung des Kantons St. Gallen mit dem Antrag, die angefochtene Verfügung aufzuheben und eine Abräumefrist von 5, eventualiter 2 Jahren festzusetzen. Sie stellten sich auf den Standpunkt, das Schreiben des Departements an die Gemeinden vom 28. September 2000 sei eine - allerdings nicht ordnungsgemäss eröffnete - Verfügung. Mit Entscheid vom 5.
Dezember 2000 trat die Regierung auf den Rekurs nicht ein, da das Schreiben vom 28. September 2000 keine anfechtbare Verfügung darstelle.
E.- Dagegen erhoben die genannten Firmen am 12. Januar 2001 Beschwerde an das Verwaltungsgericht des Kantons St. Gallen. Dieses wies mit Urteil vom 11. April 2001 die Beschwerde ab, soweit es darauf eintrat. Es erwog, mit Rekurs anfechtbar seien nur Verfügungen und Entscheide, worunter an den Einzelnen gerichtete Hoheitsakte verstanden würden, durch die eine konkrete verwaltungsrechtliche Rechtsbeziehung rechtsgestaltend oder feststellend in verbindlicher und erzwingbarer Weise geregelt werde. Das Schreiben des Departements an die Gemeinden vom 28. September 2000 sei eine organisatorische Anordnung einer Behörde an unterstellte Verwaltungseinheiten und begründe kein verwaltungsrechtliches Rechtsverhältnis. Die Betroffenen könnten allfällige gestützt auf dieses Schreiben ergehende Verfügungen der Gemeinden anfechten.
F.- Die A._ GmbH, die B._ AG, die C._ AG und die D._ haben am 8. Mai 2001 staatsrechtliche Beschwerde erhoben mit dem Antrag, den Entscheid des Verwaltungsgerichts aufzuheben und die Sache zur Neubeurteilung und neuer Entscheidung zurückzuweisen.
Sie rügen eine Verletzung von Art. 9 und 29 Abs. 1 und 2 BV.
Zudem beantragen sie Erteilung der aufschiebenden Wirkung, die mit Verfügung des Präsidenten der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 8. Juni 2001 erteilt wurde. Das Verwaltungsgericht und das Baudepartement namens der Regierung beantragen Abweisung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
1.- Die staatsrechtliche Beschwerde gegen den kantonal letztinstanzlichen, auf kantonales Recht gestützten Endentscheid ist zulässig (Art. 84 Abs. 2, Art. 86 Abs. 1 und Art. 87 OG). Die Beschwerdeführer sind legitimiert, mit staatsrechtlicher Beschwerde die Verletzung von Verfahrensvorschriften zu rügen, deren Missachtung eine formelle Rechtsverweigerung darstellt (Art. 29 Abs. 1 und 2 BV, Art. 88 OG; <ref-ruling> E. 3b S. 86, mit Hinweisen). Sie können daher geltend machen, das Verwaltungsgericht habe zu Unrecht den Nichteintretensentscheid der Regierung geschützt. Die Anwendung kantonalen Rechts unterhalb der Verfassungsstufe kann dabei vom Bundesgericht nur auf Willkür hin überprüft werden. Die Rüge der Willkür und diejenige der formellen Rechtsverweigerung fallen somit zusammen, soweit die Beschwerdeführer beanstanden, die kantonalen Instanzen seien in Verletzung kantonalen Verfahrensrechts auf ihren Rekurs nicht eingetreten.
2.- a) Die Beschwerdeführer stellen nicht in Frage, dass einzig Verfügungen Gegenstand eines Rekurses sein können.
Sie beanstanden auch nicht, dass das Verwaltungsgericht den Begriff der Verfügung im st. gallischen Recht gleich versteht wie das Bundesrecht, sondern berufen sich selber auf die Kriterien von <ref-law>. Sie bringen hingegen vor, das Schreiben des Departements vom 28. September 2000 stelle eine Verfügung in diesem Sinne dar. Es lege fest, dass die bisher gültige Rechtslage, nämlich die Zulässigkeit der fraglichen Automaten, ab 1. Dezember 2000 nicht mehr gelte; mithin werde die bisherige Rechtslage für die Beteiligten einschneidend geändert. Das Schreiben sei daher rechtsgestaltend. Es richte sich materiell an alle Automatenbetreiber und Aufsteller und könne nicht anders aufgefasst werden denn als Aufforderung, die Automaten bis zum genannten Zeitpunkt abzuräumen.
b) Glücksspielautomaten sind von Bundesrechts wegen ausserhalb von konzessionierten Spielbanken verboten (<ref-law>). Als Glücksspielautomaten gelten Geräte, welche ein im Wesentlichen automatisch ablaufendes Spiel anbieten, bei dem gegen Leistung eines Einsatzes ein Geldgewinn oder ein anderer geldwerter Vorteil in Aussicht steht, der ganz oder überwiegend vom Zufall abhängt (Art. 3 Abs. 1 und 2 SBG). Der Begriff des Glücksspielautomaten ist ein bundesrechtlicher Begriff. Die Kantone können aufgrund von Art. 3 und 106 Abs. 4 BV im Rahmen der verfassungsrechtlichen Schranken auch die Verwendung von Spielgeräten verbieten, die bundesrechtlich zugelassen sind. Sie können hingegen nicht Geräte zulassen, die unter das bundesrechtliche Verbot fallen (vgl. noch zum früheren Recht: <ref-ruling> E. 4b S. 161; Urteil des Bundesgerichts vom 11. Mai 1994, in ZBl 95/1994 S. 522 E. 2b). Einzig übergangsrechtlich können die Kantone bis zum 31. März 2005 den Weiterbetrieb von je höchstens fünf Automaten in Restaurants und anderen Lokalen zulassen, soweit diese Automaten vor dem 1. November 1997 in Betrieb waren (<ref-law>). Soweit das kantonale Recht eine solche Zulassung nicht vorsieht, sind die fraglichen Geräte von Bundesrechts wegen verboten. Die Beschwerdeführer behaupten nicht, im Kanton St. Gallen seien die streitigen Automaten im Sinne von <ref-law> übergangsrechtlich zugelassen. Im Gegenteil ist gemäss Art. 4 lit. a des kantonalen Gesetzes vom 6. Juni 1982 über Spielgeräte und Spiellokale die Verwendung von Spielgeräten verboten, wenn sie Geld oder geldwerte Gegenstände als Gewinn abgeben.
c) Dass die streitigen Geräte früher als zulässig betrachtet wurden, ergab sich nicht aus einer kantonalen Übergangsregelung im Sinne von <ref-law>, sondern daraus, dass sie nach der früheren, grosszügigen Praxis des EJPD gar nicht als Geldspielautomaten betrachtet worden waren und daher nicht der eidgenössischen Spielbankengesetzgebung unterstanden. In der Folge änderte jedoch das EJPD seine Praxis (vgl. dazu <ref-ruling>). Mit der Widerrufsverfügung vom 21. Dezember 1999 entschied es namentlich, dass die acht fraglichen Automaten entgegen seiner früheren Auffassung als Geldspielautomaten zu betrachten seien. Es legte ferner fest, dass die fraglichen Automaten bis zum 31. März 2000 noch betrieben werden dürfen. Damit setzte das EJPD bereits eine Abräumefrist fest. Das Bundesgericht legte den gegen diese Verfügungen eingereichten Beschwerden hinsichtlich der bereits aufgestellten Automaten aufschiebende Wirkung bei. Dadurch blieben die Automaten bis zum Urteil des Bundesgerichts vorläufig zulässig. Mit Urteil vom 7. Juli 2000 schützte das Bundesgericht die Qualifizierung der fraglichen Geräte als Geldspielautomaten. Das Urteil wurde an diesem Tag rechtskräftig (Art. 38 OG). Damit fiel auch die aufschiebende Wirkung der Beschwerde dahin und die Pflicht, die betreffenden Geräte abzuräumen, bestand von diesem Tag an. Das Bundesgericht hiess die Beschwerde nur insoweit teilweise gut, als es feststellte, dass die fraglichen Spielautomaten unter die Übergangsbestimmung von <ref-law> fallen. Dies hat zur Folge, dass die Kantone im Rahmen von <ref-law> die Geräte vorläufig weiterhin zulassen können. Sie sind dazu aber nicht verpflichtet.
Wenn sie von dieser Befugnis nicht Gebrauch machen, bleibt es bei der bundesrechtlichen Regelung, wonach die fraglichen Automaten ab 7. Juli 2000 ausserhalb von Grands Casinos und Kursälen unzulässig sind (<ref-law>).
Offen gelassen hat das Bundesgericht ferner die Frage, ob es sich um Glücks- oder um Geschicklichkeitsspielautomaten handelt, da diese Frage von der Eidgenössischen Spielbankenkommission zu beurteilen ist (Art. 61 der Verordnung vom 23. Februar über Glücksspiele und Spielbanken, VSBG; SR 935. 521). Indessen behaupten die Beschwerdeführer selber nicht, es handle sich um Geschicklichkeitsspielautomaten (welche gemäss <ref-law> dem kantonalen Recht unterstehen). Zudem dürfte auch ein Geschicklichkeits-Geldspielautomat nur nach vorgängigem Entscheid der Eidgenössischen Spielbankenkommission in Betrieb genommen werden (Art. 58 ff. VSBG).
Es ist somit davon auszugehen, dass es sich bei den genannten Geräten um Glücksspielautomaten im Sinne von <ref-law> handelt, die - vorbehältlich einer vorliegend nicht bestehenden kantonalen Übergangsregelung im Sinne von <ref-law> - von Bundesrechts wegen ausserhalb von Spielbanken unzulässig sind (<ref-law>).
Das Verbot ergibt sich somit nicht aus dem Schreiben des Departements vom 28. September 2000, sondern aus der Widerrufsverfügung des EJPD vom 21. Dezember 1999 bzw. aus dem Urteil des Bundesgerichts vom 7. Juli 2000, welches diese Verfügung insoweit schützte. Das Schreiben vom 28. September 2000 hat diese Rechtslage nicht gestaltet, sondern die Adressaten bloss auf die seit dem 7. Juli 2000 geltende Rechtslage hingewiesen.
d) Nach dem soeben Ausgeführten trifft die Ansicht der Beschwerdeführer nicht zu, das Volkswirtschaftsdepartement habe mit dem Schreiben vom 28. September 2000 rechtsgestaltend festgesetzt, das Verbot gelte ab 1. Dezember 2000. Das Verbot gilt von Bundesrechts wegen seit 7. Juli 2000. Das Schreiben des Volkswirtschaftsdepartements vom 28. September 2000 kann schon deshalb nicht als rechtsgestaltend betrachtet werden. Die Fristansetzung bis zum 1. Dezember 2000 erlaubt nicht den Betrieb bis zu diesem Datum, sondern legt höchstens eine Toleranzfrist fest, bis zu welcher die Behörden noch nicht eingreifen. Damit handelt es sich bei dem fraglichen Schreiben um eine Dienstanweisung generell-abstrakter Natur, welche sich an die Verwaltungsbehörden richtet und der Schaffung einer einheitlichen Verwaltungspraxis dient, aber keine für den Bürger verbindliche Regeln enthält und nicht als anfechtbare Verfügung gilt (vgl. <ref-ruling> E. 2b S. 478).
e) Das Verwaltungsgericht hat die Verfügungsqualität des Schreibens vom 28. September 2000 auch deshalb verneint, weil die Beschwerdeführer allfällige gestützt auf dieses Schreiben ergehende Verfügungen der Gemeinden anfechten könnten. In seiner Vernehmlassung an das Bundesgericht bekräftigt das Verwaltungsgericht seine Auffassung, wonach die Gemeinden das Entfernen der einzelnen Apparate mittels einer anfechtbaren Verfügung anzuordnen haben. Die Beschwerdeführer rügen diese Auffassung als willkürlich. Das Schreiben vom 28. September 2000 halte unmissverständlich fest, dass die Strafverfolgungsbehörden vom 1. Dezember 2000 an einschreiten werden; damit bleibe den Gemeinden kein Raum, mit entsprechenden Verfügungen eine verhältnismässige Abräumefrist anzuordnen.
Die Auffassung des Verwaltungsgerichts erscheint in der Tat fraglich. Dass die Apparate als Geldspielautomaten zu qualifizieren sind, ergibt sich - wie dargelegt - aus der vom Bundesgericht insoweit geschützten Verfügung des EJPD vom 21. Dezember 1999, welche im Bundesblatt publiziert worden ist (BBl 1999 9956-9963) und sich an alle Hersteller, Aufsteller und Betreiber der entsprechenden Geräte richtete.
Der Betrieb von Geldspielautomaten ist - sofern es sich um Glücksspielautomaten ausserhalb konzessionierter Spielbanken handelt - gemäss <ref-law> unmittelbar von Gesetzes wegen verboten. Ebenso gilt nach Art. 4 lit. a des st. gallischen Gesetzes über Spielgeräte und Spiellokale ein unmittelbares gesetzliches Verbot für sämtliche Spielgeräte, die Geld oder geldwerte Gegenstände als Gewinn abgeben. Da die Kantone Spielautomaten wohl enger, nicht aber grosszügiger als das Bundesrecht zulassen können (vorne E. 2b), muss diese kantonalrechtliche Bestimmung so ausgelegt werden, dass sie mindestens alle diejenigen Automaten umfasst, die bundesrechtlich als Geldspielautomaten gelten, würde das kantonale Recht doch sonst in bundesrechtswidriger Weise Geräte zulassen, die bundesrechtlich verboten sind. Vorbehalten wäre nur eine kantonale übergangsrechtliche Zulassung gemäss <ref-law>, die aber im Kanton St. Gallen nicht besteht. Ein Verbot, das unmittelbar von Gesetzes wegen gilt, braucht nicht in jedem Einzelfall durch Verfügung noch angeordnet zu werden. Allenfalls wäre eine Widerrufsverfügung erforderlich, wenn früher für einzelne Automaten ausdrücklich Betriebsbewilligungen erteilt worden wären (vgl. zit. Urteil des Bundesgerichts vom 7. Juli 2000, E. 4d), was aber im Kanton St. Gallen offenbar nicht der Fall ist.
Auch wenn die Auffassung des Verwaltungsgerichts unzutreffend sein sollte, ändert dies aber nichts daran, dass sich die entscheidende Qualifikation der Geräte als Geldspielautomaten aus den genannten Entscheiden der Bundesbehörden und die Unzulässigkeit von Geldspielautomaten unmittelbar aus dem Gesetz ergibt. So oder so war das Schreiben vom 28. September 2000 nicht rechtsgestaltend und stellte keine anfechtbare Verfügung dar. Der Rechtsschutz der Beschwerdeführer wird dadurch nicht in unzulässiger Weise verkürzt. Sie hatten die Möglichkeit, die Verfügung des EJPD vom 21. Dezember 1999 anzufechten, was sie teilweise auch getan haben. Zudem können sie im Rahmen allfälliger Strafverfahren geltend machen, es sei ihnen nach dem Urteil des Bundesgerichts vom 7. Juli 2000 nur eine unverhältnismässig kurze Frist zur Beseitigung der Automaten zur Verfügung gestanden oder die angewendeten Rechtsnormen widersprächen höherrangigem Recht.
3.- Die staatsrechtliche Beschwerde erweist sich damit als unbegründet. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten den Beschwerdeführern unter solidarischer Haftung aufzuerlegen (Art. 156 Abs. 1 und 7 OG).

Demnach erkennt das Bundesgericht:
1.- Die staatsrechtliche Beschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 4'000.-- wird den Beschwerdeführern unter solidarischer Haftung auferlegt.
3.- Dieses Urteil wird den Beschwerdeführern sowie der Regierung und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
_
Lausanne, 13. August 2001
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: