Sachverhalt:
A.
A.a. Am 16. Dezember 2011 stellte die Einwohnergemeinde Bitsch ein Gesuch für den Bau eines neuen Gebäudes auf der in der Zone für öffentliche Bauten und Anlagen gelegenen Parzelle Nr. 310, Plan 4, im Gemeindegebiet "Ze Arme Brunnu". Das Gesuch wurde im Amtsblatt Nr. 51 vom 23. Dezember 2011 publiziert. Geplant ist unter der Bezeichnung "one step more" eine mehrstöckige Baute mit insgesamt zwölf Mietwohnungen auf vier Geschossen, welche die Gemeinde zu Marktpreisen anbieten will, sowie mit einer Kindertagesstätte. Erstellt werden sollen sodann in einem offenen Raum auf Erdgeschosshöhe einige öffentliche Parkplätze. Das Gebäude soll über dem bestehenden Werkhof zu stehen kommen.
A.b. Dagegen erhoben die Ehegatten A. und B.A._ als Nachbarn der Bauparzelle am 20. Januar 2012 Einsprache. Mit Verfügung vom 19. April 2012 bewilligte die Kantonale Baukommission Wallis (KBK) das Baugesuch unter Auflagen und Bedingungen und wies die Einsprache ab.
B.
Am 27. Februar 2013 wies der Staatsrat des Kantons Wallis eine dagegen erhobene Beschwerde ab.
C.
Dagegen führten A. und B.A._ Verwaltungsgerichtsbeschwerde beim Kantonsgericht Wallis. Dieses wies die Beschwerde am 4. Oktober 2013 ab.
D.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht beantragen A. und B.A._, das Urteil des Kantonsgerichts aufzuheben.
E.
Die Einwohnergemeinde Bitsch schliesst in ihrer Vernehmlassung auf Abweisung der Beschwerde. Der Staatsrat und das Kantonsgericht stellen ohne weitere Ausführungen ebenfalls Antrag auf Abweisung.
F.
A. und B.A._ haben sich nochmals zur Sache geäussert.
G.
Mit verfahrensleitender Verfügung vom 22. November 2013 wies der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts ein Gesuch um aufschiebende Wirkung ab.

Erwägungen:
1.
1.1. Gemäss <ref-law> beurteilt das Bundesgericht Beschwerden in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung (vgl. Art. 34 Abs. 1 RPG sowie <ref-ruling> E. 1.2 S. 251; <ref-ruling> E. 1.1 S. 411). Beim angefochtenen Entscheid handelt es sich um einen anfechtbaren kantonal letztinstanzlichen Endentscheid (vgl. Art. 86 Abs. 1 lit. d und Art. 90 BGG) über eine Baubewilligung.
1.2. Die Beschwerdeführer sind als Nachbarn der Bauparzelle und als direkte Adressaten des angefochtenen Entscheides zur Beschwerde legitimiert (vgl. <ref-law>).
1.3. Mit der Beschwerde an das Bundesgericht kann, von hier nicht interessierenden Ausnahmen abgesehen, nur die Verletzung von Bundesrecht (vgl. <ref-law>) sowie die offensichtlich unrichtige Feststellung des Sachverhaltes (vgl. <ref-law>) gerügt werden. Die Vereinbarkeit des angefochtenen Entscheids mit kantonalem Recht unter Einschluss des kommunalen Rechts (mit Ausnahme des hier nicht angerufenen kantonalen Verfassungsrechts; vgl. <ref-law>) überprüft das Bundesgericht nur auf Willkür hin. Es wendet das Recht von Amtes wegen an (<ref-law>), soweit eine rechtsgenügliche Rüge erhoben wird (vgl. Art. 42 Abs. 2 sowie Art. 106 Abs. 2 BGG und <ref-ruling> E. 1.4 S. 254 f.). Es legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
2.
2.1. Die Beschwerdeführer rügen, das Kantonsgericht habe wie alle anderen Vorinstanzen keinen Augenschein durchgeführt. Entweder sei ein solcher nunmehr vom Bundesgericht vorzunehmen oder der angefochtene Entscheid sei deswegen aufzuheben und zur ergänzenden Sachverhaltsermittlung an einem Augenschein an die Vorinstanz zurückzuweisen. Die Beschwerdeführer begründen ihren Antrag im Wesentlichen damit, dass die tatsächlichen Verhältnisse nur vor Ort genau erkennbar seien.
2.2. Mit dem Verwaltungsgericht ist davon auszugehen, dass keine Verletzung des rechtlichen Gehörs vorliegt, wenn ein Gericht auf die Abnahme beantragter Beweismittel verzichtet, weil es auf Grund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener (antizipierter) Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 5.3 S. 236 f. mit Hinweisen).
2.3. Der vorliegende Fall beruht nicht auf einer Ausgangslage, deren Komplexität normale Verhältnisse übersteigt. Auch stehen keine aussergewöhnlichen Auswirkungen auf das Landschafts- oder Ortsbild in Frage. Vielmehr stören sich die Beschwerdeführer vom subjektiven Empfinden her am von der Gemeinde geplanten Bauprojekt. Entgegen ihrer Auffassung erweisen sich die tatsächlichen Umstände im vorliegenden Verfahren jedoch als in genügendem Umfange erstellt und aktenkundig. Sämtliche notwendigen Pläne sind vorhanden und Fotoaufnahmen und -montagen erlauben ein ausreichendes Bild über die entscheidwesentlichen Sachverhaltselemente. Es ist nicht davon auszugehen, dass ein Augenschein Wesentliches zur weiteren Ermittlung der sachlichen Grundlagen des Rechtsstreites beitragen könnte. Weder verstiessen demnach die Vorinstanzen und insbesondere das Kantonsgericht gegen die Verfahrensrechte des Beschwerdeführers, indem sie auf einen Augenschein verzichteten, noch erweist sich ein solcher durch das Bundesgericht als erforderlich.
3.
Die Beschwerdeführer rügen, das Kantonsgericht habe sich nicht zur Gebäudehöhe geäussert. Indessen ging die Vorinstanz beim Vergleich mit der in der umliegenden Zone W3 zulässigen Gebäudehöhe von 15 m von einer solchen des hier strittigen Bauprojekts von 16.68 m ab dem gewachsenen Terrain aus. Auch wenn aufgrund der Hanglage der für die Höhenmessung wesentliche Ausgangspunkt des gewachsenen Terrains bestimmt werden muss, erscheint die tatsächliche Einschätzung des Kantonsgerichts nicht als offensichtlich unrichtig. Die Beschwerdeführer vermögen einen solchen klaren Mangel jedenfalls nicht darzutun, weshalb die entsprechenden Feststellungen der Vorinstanz nicht zu beanstanden sind (vgl. E. 1.3).
4.
4.1. Die Beschwerdeführer machen geltend, Art. 76 des von der Urversammlung am 15. Januar 2009 angenommenen Bau- und Zonenreglements der Gemeinde Bitsch (BZR; in der von der Urversammlung am 25. November 2010 beschlossenen Fassung) widerspreche dem Bundesrecht.
4.2. Nach Art. 14 Abs. 2 RPG unterscheiden die Nutzungspläne vorab Bau-, Landwirtschafts- und Schutzzonen. Gemäss Art. 18 Abs. 1 RPG kann das kantonale Recht weitere Nutzungszonen vorsehen. Art. 24 des Gesetzes zur Ausführung des Bundesgesetzes über die Raumplanung des Kantons Wallis vom 23. Januar 1987 sieht die Möglichkeit von Zonen für öffentliche Bauten und Anlagen vor. Solche Zonen umfassen gemäss der gesetzlichen Umschreibung Gebiete, die von den Gemeinden für die Nutzung von Bauten oder Einrichtungen von öffentlichem Interesse wie Verwaltungsbauten, Spitäler, Schulen, Kirche, Mehrzweckhallen und Parkanlagen vorgesehen sind. Art. 76 BZR definiert als Zweck der Zone für öffentliche Bauten und Anlagen für die Gemeinde Bitsch die Ausscheidung von Gebieten zur Erstellung von öffentlichen Bauten und Anlagen (Schul- und Geschäftsgebäude, Sakralbauten, Bauten für Mietwohnungen) oder anderen Einrichtungen (Sport, Erholung), die im öffentlichen Interesse liegen; jegliche private Überbauung ist untersagt. Dafür gelten in Art. 76 BZR eher rudimentäre Bauvorschriften. Insbesondere sieht das Reglement keine maximale Gebäudehöhe vor, woran sich die Beschwerdeführer unter Berufung auf anders lautende Reglemente anderer Walliser Gemeinden besonders stossen. Unter der Bezeichnung "Besondere Bestimmungen" ist überdies, immer noch bezogen auf die Zone für öffentliche Bauten und Anlagen, Folgendes festgehalten:
"Der Bau von Mietwohnungen darf im Sinne der Wohnbauförderung ausschliesslich durch die Gemeinde erfolgen. Die Mietwohnungen verbleiben im Besitze der Gemeinde und dürfen nicht veräussert werden. Die Vermietung erfolgt zu Marktpreisen."
4.3. Weder das Bundesrecht noch das kantonale Recht schreiben vor, dass für die Zone für öffentliche Bauten und Anlagen reglementarisch eine maximale Gebäudehöhe festgelegt werden muss. Die Gemeinden verfügen insoweit über eine gewisse Autonomie. Dass andere Walliser Gemeinden eine solche Grenze kennen, führt daher nicht zur Rechtswidrigkeit von Art. 76 BZR.
4.4. Analoges gilt für die grundsätzliche Zulassung von gemeindeeigenen Mietwohnungen zum Zwecke des Ausbaus des entsprechenden Angebots.
4.4.1. Ein grundsätzliches Verbot kommunaler Mietwohnungen in der Zone für öffentliche Bauten und Anlagen kennen weder das Bundesrecht noch das kantonale Recht. Nach der bundesgerichtlichen Rechtsprechung sind Zonen für öffentliche Bauten und Anlagen für öffentliche oder öffentlichen Interessen dienende Bauten und Anlagen bestimmt (Urteil des Bundesgerichts 1C_310/2011 vom 10. November 2011 E. 2.5 in: ZBl 113/2012 S. 371). Entscheidend ist demnach, dass die zugelassenen Bauten und Anlagen überwiegend öffentlichen und nicht privaten Interessen dienen. Dazu zählen nebst Schulen und Sportanlagen etwa auch Alters- und Pflegeheime sowie Familiengärten, öffentliche Parkplätze und ähnliches. Ob auch Allgemeinzugänglichkeit erforderlich ist, wie die Vorinstanz grundsätzlich annimmt, hängt vom Zweck der Baute oder Anlage ab. Allgemeinzugänglichkeit kann für den öffentlichen Charakter sprechen. Je nach dem kann sie aber auch mehr oder weniger beschränkt sein, was etwa für ein Zeughaus oder Feuerwehrmagazin offensichtlich ist. In den vom Kantonsgericht dazu angerufenen Urteilen des Bundesgerichts (1P.498/2000 vom 29. März 2001 E. 4, 1A.96/2002 vom 12. Februar 2003 E. 3.4) ging es lediglich darum, das jeweils von den unteren Instanzen angerufene entsprechende Argument auf Willkür hin zu überprüfen.
4.5. Mit der Zulassung gemeindeeigener Mietwohnungen in der Zone für öffentliche Bauten und Anlagen bezweckt die Einwohnergemeinde Bitsch, dem festgestellten Mangel an Mietwohnungen auf dem Gemeindegebiet zu begegnen. Dabei geht es unter anderem darum, der Abwanderung von jungen Familien, die sich kein Eigenheim leisten können, entgegen zu wirken. Die Mietwohnungen dürfen nicht verkauft und müssen zu Marktpreisen vermietet werden. Damit soll sichergestellt werden, dass sich die Gemeinde im Verhältnis zu den Anbietern privater Mietwohnungen, die es trotz des Mangels solcher Wohnungen gibt, wettbewerbsneutral verhält und dass die Wohnungen nicht ins Privateigentum übergehen. Die Erstellung gemeindeeigener Mietwohnungen unter den reglementarisch vorgeschriebenen Kautelen liegt mithin im öffentlichen Interesse, auch wenn die Wohnungen naturgemäss nicht allgemeinzugänglich sind.
5.
5.1. Die Auslegung und Anwendung von Art. 76 BZR kann vom Bundesgericht nur auf Willkür hin überprüft werden (vgl. E. 1.3).
5.2. Auch wenn im kommunalen Reglement keine maximale Gebäudehöhe festgelegt ist, bedeutet das nicht, dass die Gebäudehöhe bei öffentlichen Bauten und Anlagen völlig frei wäre. Die Vorinstanz hat dazu einen Vergleich mit der umliegenden Wohnzone W3 gezogen und festgehalten, die für das strittige Bauvorhaben geplante Höhe von 16.68 m weiche nicht erheblich von der in unmittelbarer Nähe geltenden maximalen Höhe von 15 m ab. Das ist nicht unhaltbar.
5.3. Die Beschwerdeführer rügen weiter, die Baute liege nicht im öffentlichen Interesse, wie dies Art. 76 BZR vorschreibe. Die strittige Erstellung von Mietwohnungen zu Marktpreisen entspricht aber angesichts der entsprechenden Mangellage durchaus einem öffentlichen Interesse und ist mit Art. 76 BZR vereinbar. Die geplanten Mietwohnungen bleiben im Eigentum der Gemeinde, was ebenfalls mit Art. 76 BZR im Einklang steht. Die eingegangenen Vorreservationen übersteigen anscheinend bereits das geplante Angebot, was den fraglichen Bedarf und damit das öffentliche Interesse unterstreicht. Darüber hinaus entsprechen auch die vorgesehene Kindertagesstätte sowie die geplanten öffentlichen Parkplätze im Erdgeschoss dem öffentlichen Interesse. Schliesslich soll das Bauvorhaben als Aufbau auf dem Werkhof mit Feuerwehr im Untergeschoss errichtet werden, wobei es sich um eine weitere Baute im öffentlichen Interesse handelt.
5.4. Die Auslegung und Anwendung von Art. 76 BZR ist demnach nicht willkürlich.
6.
Schliesslich machen die Beschwerdeführer vor Bundesgericht neu geltend, es sei zu überprüfen, ob der Bau nicht gegen die verfassungsrechtliche Zweitwohnungsbeschränkung nach <ref-law> verstosse. Ob diese neue Rüge überhaupt zulässig ist, kann offen bleiben. Mit dem Bauprojekt sollen offensichtlich nicht Zweitwohnungen, sondern Erstwohnungen für die einheimische Bevölkerung in Dauermietverhältnissen erstellt werden. Die Gemeinde wird allerdings darauf behaftet, bei der Vermietung auch darauf zu achten.
7.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen.
Bei diesem Verfahrensausgang werden die unterliegenden Beschwerdeführer unter Solidarhaft kostenpflichtig (Art. 66 Abs. 1 und 5, <ref-law>). Eine Parteientschädigung ist der obsiegenden Gemeinde entgegen ihrem entsprechenden Antrag praxisgemäss nicht zuzusprechen (vgl. <ref-law> sowie <ref-ruling> E. 7 S. 118 f.).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern unter Solidarhaft auferlegt.
3.
Dieses Urteil wird den Beschwerdeführern, der Einwohnergemeinde Bitsch, dem Staatsrat des Kantons Wallis und dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 21. März 2014
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Uebersax