Motzkin paths of order are a generalization of Motzkin paths that use steps U=(1,1), L=(1,0), and D_i=(1,-i) for every positive integer . We further generalize order- Motzkin paths by allowing for various coloring schemes on the edges of our paths. These -colored Motzkin paths may be enumerated via proper Riordan arrays, mimicking the techniques of Aigner in his treatment of "Catalan-like numbers". After an investigation of their associated Riordan arrays, we develop bijections between -colored Motzkin paths and a variety of well-studied combinatorial objects. Specific coloring schemes allow us to place -colored Motzkin paths in bijection with different sub-classes of generalized k-Dyck paths, including k-Dyck paths that remain weakly above horizontal lines y=-a, k-Dyck paths whose peaks all have the same height modulo-k, and Fuss-Catalan generalizations of Fine paths. A general bijection is also developed between -colored Motzkin paths and certain sub-classes of k-ary trees.