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 Art. 60 SBG 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.