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. 