Sachverhalt: A. Das Departement für Verkehr, Bau und Umwelt des Kantons Wallis schrieb im Amtsblatt vom 18. Mai 2007 den Bau des Autobahntunnels Eyholz im offenen Verfahren aus, wobei Teilangebote und Projektvarianten nicht zugelassen waren. In den Ausschreibungsunterlagen wurde den Anbietern insbesondere die Auflage gemacht, beim Bau des Tunnels Kies aus der Region zu beziehen. Mit Entscheid des Staatsrats des Kantons Wallis vom 19. Dezember 2007 erhielt die "ARGE Haupttunnel Eyholz" den Zuschlag. Diese beauftragte in der Folge die Z._AG mit der Kieslieferung. Mit Entscheid vom 12. Mai 2010 genehmigte der Staatsrat die Errichtung einer Kies- und Betonwerkanlage auf der Parzelle Nr. 7521 in der Gemeinde Leuk durch die Z._AG und erteilte dieser die Bewilligung zur Ausbeutung der erforderlichen Menge Kies für den Tunnelbau. B. Gegen diesen Entscheid reichten die X._AG und die Y._AG am 16. Juli 2010 beim Kantonsgericht Wallis Verwaltungsgerichtsbeschwerde ein. Mit Urteil vom 17. März 2011 trat das Kantonsgericht auf die Beschwerde nicht ein. C. Die X._AG und die Y._AG führen Beschwerde in öffentlich-rechtlichen Angelegenheiten und subsidiäre Verfassungsbeschwerde ans Bundesgericht mit den Anträgen, das Urteil des Kantonsgerichts vom 17. März 2011 aufzuheben, die Legitimation der Beschwerdeführerinnen zur Anfechtung des Entscheids des Staatsrats vom 12. Mai 2010 zu bejahen und diesen Entscheid aufzuheben. Eventualiter sei die Sache zur materiellen Behandlung an die Vorinstanz zurückzuweisen. Das Kantonsgericht stellt Antrag auf Beschwerdeabweisung. Der Staatsrat verzichtet auf eine Vernehmlassung. Die Z._AG beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei diese abzuweisen. Mit Präsidialverfügung vom 29. Juli 2011 wies das Bundesgericht das Gesuch der Beschwerdeführerinnen um Erlass einer vorsorglichen Massnahme (Einstellung der Arbeiten für die Erstellung der Kies- und Betonwerkanlage) ab. In ihrer Stellungnahme vom 31. August 2011 halten die Beschwerdeführerinnen an ihrem Standpunkt fest.