Let D_v the difference operator and q-difference operators defined by D_\omega p(x) = \frac{p(x+\omega)-p(x)}{\omega} and D_q p(x) = \frac{p(qx)-p(x)}{(q-1)x}, respectively. Let U and V be two moment regular linear functionals and let (P_n)_n and Q_n)_n be their corresponding orthogonal polynomial sequences (OPS). We discuss an inverse problem in the theory of discrete orthogonal polynomials involving the above two OPS assuming that their difference derivatives D_\nu of higher orders m and k (resp.) are connected by a linear algebraic structure relation such as \sum_{i=0}^M a_{i,n} D_\nu^m P_{n+m-i}(x) = \sum_{i=0}^N b_{i,n} D_\nu^k Q_{n+k-i}(x), \quad n\geq 0, where $M,N,m,k=0,1,2,... Under certain conditions, we prove that U and V are related by a rational factor \c{c} (in the distributional sense). Moreover, when m\neq k then both U and V are D_v-semiclassical functionals. This leads us to the concept of (M,N)-D_v-coherent pair of order (m,k) extending to the discrete case several previous works. As an application we consider the OPS with respect to a certain following Sobolev-type discrete inner product.