In this paper, we introduce a novel coding and decoding framework based on a generalized form of the k-order Jacobsthal polynomials. To this end, we first investigate the structure of these polynomials and derive a general expression for the powers of their associated companion matrices. Specifically, we develop a coding/decoding scheme utilizing integer powers of the companion matrix Qk (x) whose entries are determined by the coefficients of the k-order Jacobsthal polynomials. Furthermore, we define a suitable alphabet structured by generalized Jacobsthal numbers, integrating this alphabet into the proposed coding methodology. This construction enables a new perspective on algebraic coding theory by embedding the properties of k-order Jacobsthal polynomials into the design of the coding system. To demonstrate the practicality of the method, several illustrative examples and applications are presented. Finally, potential directions for future research and implications for coding theory are discussed.