The foundational work of Karlin and McGregor established a powerful connection between random walks with tridiagonal transition matrices and the theory of orthogonal polynomials. We consider a particular extension of this framework, where the transition matrix is given by a polynomial in a tridiagonal matrix. This generalization leads to transitions beyond the nearest neighbors. We investigate the matrix-valued orthogonal polynomials associated with these extended models, derive the corresponding matrix-valued measure of orthogonality explicitly, and analyze how spectral properties of the transition matrix relate to probabilistic features of the random walk. As an application, we study generalized Ehrenfest models that incorporates longer-range transitions.