Art. 9 BV (Beschwerdelegitimation), hat sich ergeben:
A.- Die Luzern-Stans-Engelberg-Bahn hat am 14. Juli 2000 die "Baulose Nord und Süd" (Tunnelbauarbeiten bei Engelberg im Rahmen des "Neubaus Steilrampe") an die Arbeitsgemeinschaft A._/Z. _ vergeben.
B.- Hiergegen beschwerte sich der Verein Paritätische Berufskommission für das Bauhauptgewerbe Unterwalden beim Verwaltungsgericht des Kantons Nidwalden. Er machte geltend, die Arbeiten dürften nicht an die ARGE A._/Z. _ vergeben werden, weil die Z._ & Co. keine Gewähr für die Einhaltung der arbeitsgesetzlichen und landesmantelvertraglichen Normen biete, habe sie diese doch bereits andernorts grob verletzt. Das Verwaltungsgericht trat mangels Legitimation des Vereins auf dessen Beschwerde nicht ein (Entscheid vom 11. Dezember 2000).
C.- Am 7. Februar 2001 ist der Verein Paritätische Berufskommission für das Bauhauptgewerbe Unterwalden mit staatsrechtlicher Beschwerde an das Bundesgericht gelangt.
Er rügt eine Verletzung des Willkürverbots (Art. 9 BV) und beantragt, der Entscheid des Verwaltungsgerichts des Kantons Nidwalden sei aufzuheben und die Sache zur Neubeurteilung (im Sinne gewisser Zusatzanträge des Beschwerdeführers) an dieses zurückzuweisen.
Die Luzern-Stans-Engelberg-Bahn beantragt Abweisung der Beschwerde, soweit auf diese eingetreten werden könne.
Das Verwaltungsgericht hat auf eine Stellungnahme verzichtet, während sich die ARGE A._/Z. _ nicht hat vernehmen lassen.

Das Bundesgericht zieht in Erwägung:
1.- a) Angefochten ist ein kantonal letztinstanzlicher Endentscheid, der sich auf kantonales Recht stützt und gegen den im Bund nur die staatsrechtliche Beschwerde offen steht (Art. 86 Abs. 1 und Art. 87 in Verbindung mit Art. 84 Abs. 2 OG).
b) Der Beschwerdeführer verfügt als Verein über eine eigene Rechtspersönlichkeit (vgl. Art. 60 f. ZGB). Er ist, unabhängig von der Legitimation in der Sache, befugt, mittels staatsrechtlicher Beschwerde zu rügen, das kantonale Verwaltungsgericht sei auf sein Rechtsmittel gegen den Vergebungsentscheid in verfassungswidriger Weise nicht eingetreten (vgl. <ref-ruling> E. 3c S. 312 f.). Einzig diese Frage bildet Gegenstand des bundesgerichtlichen Verfahrens.
Es fragt sich allerdings, wieweit der Beschwerdeführer über ein aktuelles Interesse an der Anfechtung des streitigen Nichteintretensentscheids verfügt: Nachdem der Vertrag zwischen der Luzern-Stans-Engelberg-Bahn und der ARGE A._/Z. _ inzwischen abgeschlossen worden ist, könnte auch eine Gutheissung der staatsrechtlichen Beschwerde am Gang der Dinge nichts mehr ändern: Gemäss Art. 9 Abs. 3 des Bundesgesetzes vom 6. Oktober 1995 über den Binnenmarkt (BGBM; SR 943. 02) hat die Rechtsmittelinstanz, falls der Vertrag mit dem Anbieter bereits abgesschlossen worden ist, lediglich festzustellen, inwiefern die angefochtene Verfügung Bundesrecht verletzt. Wird eine Rechtsverletzung bejaht, so steht dem betroffenen Konkurrenten die Geltendmachung von Schadenersatz offen (<ref-ruling> E. 5b S. 97 f.; vgl. auch Art. 18 des Nidwaldner Gesetzes vom 7. Februar 2001 über das öffentliche Beschaffungswesen [Submissionsgesetz; SubG/NW], dessen Inkraftsetzung unmittelbar bevorsteht). Für den Beschwerdeführer, der sich nicht als Anbieter am Vergabeverfahren beteiligt hat, fällt ein Schadenersatzanspruch zum Vornherein ausser Betracht. Vorliegend kann jedoch auf das Erfordernis des aktuellen Interesses verzichtet werden, weil sich die gleiche prozessuale Situation für den Beschwerdeführer auch in künftigen Beschwerdeverfahren ergeben könnte. Deshalb ist vorliegend über die streitige Legitimationsfrage zu entscheiden (<ref-ruling> E. 1b S. 252, mit Hinweisen).
c) Die staatsrechtliche Beschwerde ist, von hier nicht in Betracht fallenden Ausnahmen abgesehen, rein kassatorischer Natur (<ref-ruling> E. 1b S. 107, mit Hinweisen; grundlegend <ref-ruling> E. 4 S. 332 ff.). Soweit vorliegend mehr als die Aufhebung des angefochtenen Entscheids verlangt wird, ist daher auf die Eingabe des Beschwerdeführers nicht einzutreten.
d) Die staatsrechtliche Beschwerde muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Entscheid verletzt worden sind (Art. 90 Abs. 1 lit. b OG). Das Bundesgericht untersucht nicht von Amtes wegen, ob ein kantonaler Hoheitsakt verfassungsmässig ist, sondern prüft nur rechtsgenügend vorgebrachte, klar erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 2 S. 3 f.; <ref-ruling> E. 1d S. 201, mit Hinweisen). Wird eine Verletzung des Willkürverbots (Art. 9 BV) geltend gemacht, genügt es nicht, wenn der Beschwerdeführer bloss den angefochtenen Entscheid kritisiert, wie er dies in einem appellatorischen Verfahren tun könnte, bei dem die Rechtsmittelinstanz die Rechtsanwendung frei überprüfen kann. Er muss deutlich dartun, welche Vorschriften oder allgemein anerkannten Rechtsgrundsätze die kantonalen Behörden in einer gegen Art. 9 BV verstossenden Weise verletzt haben sollen (<ref-ruling> E. 4b S. 12, mit Hinweis). Soweit die weitschweifige, zum Teil schwer verständliche Beschwerdeschrift diesen Anforderungen nicht genügt und sich in appellatorischer Kritik erschöpft, ist auf sie nicht einzugehen.
2.- a) Der Beschwerdeführer rügt, die Verneinung seiner Legitimation durch das Verwaltungsgericht verletze das Willkürverbot.
Seine Mitglieder seien die Sektion Unterwalden des Schweizerischen Baumeisterverbands, die Sektion Zentralschweiz der Gewerkschaft Bau und Industrie sowie der Kreis Ob- und Nidwalden des Christlichen Holz- und Bauarbeiterverbands.
Es gehöre zu seinen statutarischen Aufgaben, die Normen des Landesmantelvertrags für das schweizerische Bauhauptgewerbe durchzusetzen, insbesondere auch im Hinblick auf das Submissionswesen. In dieser Eigenschaft müsse er verhindern können, dass die Luzern-Stans-Engelberg-Bahn die fraglichen Arbeiten an die ARGE A._/Z. _ vergebe, weil die an dieser beteiligte Z._ & Co. andernorts bereits mehrfach gegen Bestimmungen des Arbeitsgesetzes und des Landesmantelvertrags verstossen habe. Er sei deshalb legitimiert, gegen den streitigen Vergebungsentscheid Beschwerde zu führen.
b) Ein Hoheitsakt verstösst dann gegen das Willkürverbot (Art. 9 BV), wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Er ist nicht schon dann willkürlich, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre (vgl. <ref-ruling> E. 4a S. 5, mit Hinweisen).
c) Das Verwaltungsgericht hat die Legitimation des Vereins Paritätische Berufskommission für das Bauhauptgewerbe Unterwalden zur Anfechtung des Zuschlags verneint.
Der Beschwerdeführer sei nicht am Vergabeverfahren beteiligt gewesen und mithin nicht Adressat des Vergebungsentscheids.
Er könne sich auf keine gesetzliche Bestimmung stützen, die ihn trotzdem zur Anfechtung des Entscheids legitimiere. Auch eine Verbandsbeschwerde des Vereins im Interesse seiner Mitglieder sei nicht zulässig: Aus den Statuten des Beschwerdeführers ergebe sich nicht, dass dieser im Rahmen der "Beratung und Durchführung von Massnahmen im Zusammenhang mit dem Submissionswesen" auch zur Interessenwahrung der Mitglieder mittels Verbandsbeschwerde befugt sei. Im Übrigen fänden ausschliesslich das GATT/WTO-Übereinkommen vom 15. April 1994 über das öffentliche Beschaffungswesen (SR 0.632. 231.422; für die Schweiz in Kraft seit 1. Januar 1996) und das Bundesgesetz vom 6. Oktober 1995 über den Binnenmarkt (BGBM; SR 943. 02) Anwendung, die beide keine Arbeitnehmerschutzvorschriften enthielten; die Interkantonale Vereinbarung vom 25. November 1994 über das öffentliche Beschaffungswesen (IVoeB; SR 172. 056.4) habe im Kanton Nidwalden noch keine Geltung erlangt.
d) Das Binnenmarktgesetz verpflichtet die Kantone, wenigstens ein Rechtsmittel an eine verwaltungsunabhängige kantonale Beschwerdeinstanz vorzusehen (Art. 9 Abs. 2 BGBM); im Konkordat (Art. 15 Abs. 1 IVoeB) und im erwähnten GATT/ WTO-Übereinkommen (Art. XX) finden sich analoge Bestimmungen.
Wer zum Ergreifen dieses Rechtsmittels befugt ist, beantwortet sich jedoch vorab nach dem einschlägigen kantonalen Recht (Peter Galli/Daniel Lehmann/Peter Rechsteiner, Das öffentliche Beschaffungswesen in der Schweiz, Zürich 1996, N 580). Der Beschwerdeführer verkennt in diesem Zusammenhang, dass er nicht direkt aus dem Konkordat ein Beschwerderecht ableiten kann; deshalb ist unerheblich, ob die Bestimmungen der Interkantonalen Vereinbarung über das öffentliche Beschaffungswesen im Kanton Nidwalden bereits Anwendung fanden, als der angefochtene Entscheid getroffen wurde. Immerhin folgt aus dem Zweck des Binnenmarktgesetzes und aus dem Wortlaut von Art. XX des GATT/WTO-Übereinkommens ohne weiteres, dass zumindest die übergangenen oder ausgeschlossenen Submittenten beschwerdelegitimiert sein müssen.
Umgekehrt besteht für Unternehmungen, die sich am Verfahren nicht beteiligt haben, regelmässig kein Rechtsschutzinteresse an der Anfechtung des Vergebungsentscheids. Wieweit am Submissionsverfahren nicht beteiligte Dritte, etwa interessierte Verbände, aus besonderen Gründen zur Beschwerde berechtigt sein könnten, ist fraglich. Dies gilt auch für die paritätischen Kommissionen, die - wie der Beschwerdeführer - eingesetzt werden, um die Einhaltung der Gesamtarbeitsverträge zu kontrollieren (vgl. Edwin Schweingruber/ F. Walter Bigler, Kommentar zum Gesamtarbeitsvertrag,
3. Auflage, Bern 1985, S. 113). Sie sind weder durch das Bundesgesetz vom 28. September 1956 über die Allgemeinverbindlicherklärung von Gesamtarbeitsverträgen (AVEG; SR 221. 215.311) noch durch anderes Bundesrecht ermächtigt, in Ausübung ihrer Kontrollfunktionen Beschwerde zu führen.
Es erscheint denn auch eher ihren Aufgaben angepasst, die Einhaltung der Arbeitnehmerschutzbestimmungen (vgl. Art. 11 lit. e IVoeB) durch die Submittenten (vor und nach dem Vergebungsentscheid) zu überwachen und allfällige Missstände den zuständigen kantonalen Behörden anzuzeigen (vgl. zur Rechtslage im Kanton Graubünden: Alberto Crameri, Neuerungen im öffentlichen Beschaffungswesen, in: ZGRG 15/1996 S. 13; Agostino Priuli, Die Rechtsprechung zum Submissionswesen, in: ZGRG 3/1984 S. 67 f.). Aufgrund des Dargelegten ist die Legitimation des Beschwerdeführers gestützt auf das kantonale Verwaltungsverfahrensrecht und nach den allgemeinen Regeln zu beurteilen (vgl. Galli/Lehmann/Rechsteiner, a.a.O., N 540).
e) aa) Die Legitimation zur Verwaltungsgerichtsbeschwerde wird in § 70 der Nidwaldner Verordnung vom 8. Februar 1985 über das Verwaltungsverfahren und die Verwaltungsrechtspflege (Verwaltungsrechtspflegeverordnung; VRPV) umschrieben, welche Regelung auch unter der Herrschaft des kantonalen Submissionsgesetzes massgebend sein wird (vgl. Art. 11 SubG/NW): Beschwerde erheben kann, wer ein rechtliches oder tatsächliches, schutzwürdiges Interesse an der Aufhebung oder Änderung eines Entscheids hat (Ziff. 1) sowie jede andere natürliche oder juristische Person oder Behörde, welche von der Gesetzgebung dazu ermächtigt wird (Ziff. 2). Da sich diese Regelung (weitestgehend) mit jener von Art. 103 OG und den entsprechenden Bestimmungen in anderen kantonalen Verfahrensordnungen deckt, kann für die Beurteilung der vorliegenden Streitigkeit auf die Grundsätze zurückgegriffen werden, welche die schweizerische Rechtspraxis zur Beschwerdelegitimation entwickelt hat.
bb) In erster Linie sind es die Adressaten einer Verfügung, welche befugt sind, diese anzufechten; der Beschwerdeführer gehört vorliegend nicht zu diesem Kreis. Es können jedoch auch Dritte zur Beschwerdeführung gegen eine Verfügung legitimiert sein: Damit ihnen ein ausreichendes Rechtsschutzbedürfnis zukommt, müssen sie durch die streitige Anordnung unmittelbar berührt sein und eine spezifische Beziehungsnähe zur Streitsache haben (<ref-ruling> E. 2a S. 177 f.; <ref-ruling> E. 2a S. 51, je mit Hinweisen). Dies ist jedenfalls dann nicht der Fall, wenn ein interessierter Dritter den Vergebungsentscheid zugunsten eines Verfügungsadressaten anfechten will: Akzeptieren die am Verfahren beteiligten Konkurrenten die Vergabe an einen anderen Anbieter, so können Dritte - z.B. Arbeitnehmer oder Lieferanten als Vertragspartner der übergangenen Bewerber - kein eigenes Beschwerderecht haben. Es verhält sich insofern gleich wie mit dem Nachbarn, der nicht anstelle des Bauherrn gegen die Abweisung des Baugesuchs rekurrieren kann. Zu Recht beruft sich der Beschwerdeführer deshalb nicht auf die übergangenen Konkurrenten der ARGE A._/Z. _, unter denen sich auch Mitglieder der ihm angeschlossenen Sektion des Baumeisterverbands befinden. Weiter ist er als (ideeller) Verein durch den Entscheid darüber, an wen die fraglichen Arbeiten vergeben werden, selbst nicht unmittelbar berührt. Nachdem er nicht geltend macht, gestützt auf eine spezialgesetzliche Bestimmung im Sinne von § 70 Ziff. 2 VRPV direkt zur Beschwerdeführung befugt zu sein (sog. ideelle Verbandsbeschwerde), bleibt einzig zu prüfen, ob er zur Wahrung der Interessen seiner Mitglieder Beschwerde erheben konnte (sog. egoistische Verbandsbeschwerde) bzw. ob das Verwaltungsgericht ihm die entsprechende Legitimation in Verletzung des Willkürverbots abgesprochen hat.
cc) Das Verwaltungsgericht des Kantons Nidwalden anerkennt die Befugnis einer Vereinigung, zur Wahrung der Interessen ihrer Mitglieder Beschwerde zu führen, unter den gleichen Voraussetzungen, wie sie nach der Rechtsprechung des Bundesgerichts für das Verfahren der eidgenössischen Verwaltungsgerichtsbeschwerde und der staatsrechtlichen Beschwerde gelten: Erforderlich ist, dass die fragliche Vereinigung über juristische Persönlichkeit verfügt, dass die Mehrheit oder doch eine grosse Anzahl ihrer Mitglieder von der Verfügung berührt ist und selbst zur Beschwerde berechtigt wäre und dass die Vereinigung nach ihren Statuten mit der Wahrung der in Frage stehenden Interessen ihrer Mitglieder beauftragt ist (anstelle vieler:
BGE 122 I 90 E. 2c S. 92; <ref-ruling> E. 2d/aa S. 46, je mit Hinweisen).
Diese Voraussetzungen sind beim Beschwerdeführer offensichtlich nicht erfüllt: Die beiden Gewerkschaftssektionen, welche zusammen mit der Sektion des Baumeisterverbands den Verein bilden, sind ihrerseits nur dann zur Beschwerde legitimiert, wenn diese Befugnis auch zumindest einer Grosszahl ihrer Mitglieder zukommt. Selbst wenn diese zum Teil bei Baufirmen angestellt sein sollten, welche sich am Vergebungsverfahren beteiligt hatten, wären sie selber nicht legitimiert, den Submissionsentscheid anstelle ihres Arbeitgebers anzufechten. Die Eigenschaft, Arbeitnehmer eines im Submissionsverfahren übergangenen Unternehmens zu sein, begründet kein unmittelbares eigenes Interesse an der Anfechtung des Zuschlags (vgl. oben, E. 2e/bb). Noch weniger können Gewerkschaftsmitglieder beschwerdeberechtigt sein, welche von Bauunternehmen beschäftigt werden, die sich am Submissionsverfahren nicht beteiligt hatten. Soweit der Beschwerdeführer diesbezüglich mit einer "virtuellen Betroffenheit" argumentiert, scheint er zu verkennen, dass die von ihm zitierten Entscheide Verfahren der abstrakten Normenkontrolle betreffen, für welche die Beschwerdelegitimation anders umschrieben wird (anstelle vieler: <ref-ruling> E. 1b S. 73; <ref-ruling> E. 1b S. 200) als bei der Überprüfung von Einzelakten. Ein Rechtsschutzinteresse an der Anfechtung von Einzelakten kommt nur dem unmittelbar und nicht auch dem bloss indirekt Betroffenen zu, wie der Beschwerdeführer zu glauben scheint.
Auch für die Sektion Unterwalden des Schweizerischen Baumeisterverbands, welche dem Beschwerdeführer als drittes Mitglied angehört, käme eine Legitimation nur dann in Frage, wenn die an der Submission beteiligten Bauunternehmungen zugleich die Grosszahl der Mitglieder dieser Sektion ausmachen würden. Gleich wie bezüglich der Gewerkschaftssektionen wird nicht dargetan, dass diese Voraussetzung für die Zulässigkeit der (egoistische) Verbandsbeschwerde erfüllt ist.
3.-a) Nach dem Gesagten konnte das Verwaltungsgericht ohne Willkür entscheiden, der Beschwerdeführer sei nicht zur Anfechtung des Vergebungsentscheids legitimiert. Die staatsrechtliche Beschwerde ist mithin unbegründet, soweit darauf einzutreten ist.
b) Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig.
Obsiegenden Behörden oder mit öffentlichen Aufgaben betrauten Organisationen wird in der Regel keine Parteientschädigung zugesprochen (analog zu Art. 159 Abs. 2 OG). In Anbetracht der Tatsache, dass die Vergabe von Aufträgen nicht üblichem hoheitlichem Handeln entspricht und die Umstände vorliegend ein Abweichen von der Regel rechtfertigen, hat der Beschwerdeführer der anwaltlich vertretenen Beschwerdegegnerin für das bundesgerichtliche Verfahren eine angemessene Entschädigung auszurichten.

Demnach erkennt das Bundesgericht:
1.- Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Die Gerichtsgebühr von Fr. 3'000.-- wird dem Beschwerdeführer auferlegt.
3.- Der Beschwerdeführer hat die Luzern-Stans-EngelbergBahn für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.- Dieses Urteil wird den Parteien und dem Verwaltungsgericht (Verwaltungsabteilung) des Kantons Nidwalden schriftlich mitgeteilt.
Lausanne, 8. Juni 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: