Faits : A. A.a. L'art. 8 let. c de la loi [du canton du Valais] du 20 janvier 1953 sur la police cantonale (RS/VS 550.1) donne au Conseil d'Etat la compétence de fixer par ordonnance le traitement, le logement, les indemnités et les congés. Se fondant sur cette délégation, le Conseil d'Etat a adopté l'ordonnance du 20 décembre 1995 concernant le traitement des membres du corps de la police cantonale (OTMPC; RS/VS 550.110). L'art. 3 al. 1 de cette ordonnance dispose que le traitement de base est fixé dans le cadre de l'échelle des traitements de l'administration cantonale. L'art. 12 al. 4 OTMPC a la teneur suivante: "Pour le policier nouvellement nommé qui bénéficie d'une expérience professionnelle ou autre déjà acquise, le Conseil d'Etat fixe l'augmentation initiale, compte tenu de la nature et de la durée de l'activité antérieure." L'échelle des traitements de l'année 2000 de l'administration cantonale, établie par le Département cantonal des finances, prévoyait à ce propos que l'activité antérieure d'un nouveau collaborateur était prise en considération de la manière suivante: - activité antérieure identique ou analogue: 2 % par an; - activité antérieure partiellement comparable: 1 % par an; - activité antérieure sans rapport: 0, 5 % par an. A cette époque et selon cette échelle des traitements, un système dit de paliers d'attente était en vigueur pour des raisons financières. Il s'agissait d'une réduction du traitement défini alors selon deux paliers, de 6 % (classes de salaire A1 à 21; premier palier) et de 4 % (classes de salaire 22 à 26; deuxième palier). A.b. A._, née en _, a été nommée au grade de gendarme par le Conseil d'Etat du Valais, tout d'abord à titre provisoire en 1999, puis à titre définitif en 2000. Lors de sa nomination, elle a été colloquée en classe 18 et soumise à un palier d'attente de 6 %. Il n'a pas été tenu compte de son activité antérieure d'employée de bureau (parts d'expérience). Au cours de sa carrière au sein de la police, A._ a été promue successivement aux grades d'appointé, puis de caporal, et enfin de sergent avec effet au 1 er janvier 2013. A.c. Le 2 juillet 2003, A._, se référant à des "courriers similaires de plusieurs collègues", a demandé au commandant de la police valaisanne la prise en compte dans son traitement initial, sous la forme de parts d'expérience, des quatre années durant lesquelles elle avait travaillé comme employée de commerce entre 1994 et 1998. Le 28 août 2003, cette requête a fait l'objet d'une détermination du service juridique de l'ancien Département des finances, de l'agriculture et des affaires extérieures. Celui-ci l'a considérée comme dénuée de fondement, attendu que la question avait été traitée au moment de l'engagement de l'intéressée et qu'il n'y avait pas lieu d'y revenir plusieurs années plus tard, les conditions d'une révision n'étant au demeurant pas réalisées. Cette détermination a été communiquée à la fonctionnaire le 24 septembre 2003. Celle-ci a par la suite vainement réitéré sa requête, ce qui a conduit le juriste de l'état-major de la police cantonale a confirmer le refus de l'Etat et à "mettre un terme à (la) procédure" (lettre du 23 mai 2007). Après avoir encore entrepris sans succès diverses démarches, notamment auprès du Président du Conseil d'Etat et de la conseillère d'Etat en charge du Département de la sécurité, des affaires sociales et de l'intégration, A._ a adressé le 28 décembre 2012 une lettre au Conseil d'Etat pour lui faire part de son incompréhension face au refus des autorités, alors même que, selon ses affirmations, une augmentation de traitement avait été accordée à d'autres collaborateurs entrés après elle au service de la police. Elle demandait que son traitement fût augmenté de 4 % avec effet à la date de son engagement. Statuant le 20 février 2013, le Conseil d'Etat a refusé d'entrer en matière au motif qu'une reconsidération heurterait le principe de la sécurité juridique, qu'elle engendrerait des corrections avec effet rétroactif sur plusieurs années du traitement et des cotisations d'assurances sociales, incompatibles avec le principe comptable de l'annualité et, qu'enfin, elle irait à l'encontre de la responsabilisation des membres du personnel de la fonction publique dont on pouvait attendre qu'ils manifestent en temps utile leur désaccord avec leurs conditions salariales. B. B.a. Par arrêt du 14 mai 2013, le Tribunal fédéral a déclaré irrecevable le recours formé contre cette décision par A._. Il a considéré que la décision attaquée n'émanait pas d'une autorité judiciaire supérieure. Il a transmis la cause à l'autorité judiciaire qui paraissait normalement compétente, à savoir la Cour de droit public du Tribunal cantonal du canton du Valais (cause 8C_240/2013). B.b. Saisie du litige à la suite de cet arrêt, la Cour de droit public du Tribunal cantonal valaisan a rejeté le recours en confirmant le refus d'entrer en matière du Conseil d'Etat (jugement du 9 août 2013). C. A._ exerce un recours en matière de droit public contre ce jugement, dont elle demande l'annulation. Elle conclut, principalement, au renvoi de la cause à l'autorité précédente. Subsidiairement, elle demande à être mise au bénéfice, avec effet rétroactif sur cinq ans et pour l'avenir, "de l'augmentation initiale à raison de 1 % par an pour 4 ans, soit 4 %". Le Conseil d'Etat conclut au rejet du recours.