Python 2, 296 277 245

Python 3, 200 194 170 bytes

from numpy import*
def f(p,s='',*u):
 while any(ediff1d(p)<0):(p,s,i),*u=*u,*[(r_[p],s+f'v{v}',(s_[:],v))for v in r_[:len(p[1])]],(p,s+'>0',0);p[i]=roll(p[i],1)
 return s

Try it online! or Try a faster version

-19: unicode arrows weren't required...
-32: slightly reworked, but much slower performance on average.
-45: took some inspiration from @Arnauld's answer. Switched to Python 3 for f'' (-4 bytes)
-6: range( )→r_[: ], diff(ravel( ))→ediff1d( )
-24: s_, assorted improvements

Searches combinations of all possible ↓ moves and →0. Times out on the third test case.

Since →n is equivalent to

↓0↓1...↓(c-1) 	... repeated r-n times
→0
↓0↓1...↓(c-1)	... repeated n times

where r and c are the numbers of rows and columns, these moves are sufficient to find every solution.

from numpy import*
def f(p,s='',u=[]):                         # s: moves taken, u: queue
    while any(ediff1d(p)<0):                # while p not sorted
        (p,s,i),*u=                         # pop from queue
            *u,                             #   and append:
            *[(r_[p],s+f'v{v}',(s_[:],v))   #     p,↓v
              for v in r_[:len(p[1])]],     #       for all columns v
            (p,s+'>0',0)                    #     p,→0
        p[i]=roll(p[i],1)                   # transform p
    return s                                #return the moves taken

>v correspond to →↓, respectively.

Jelly, 35 bytes

ṙ€LXȮƊ¦1
ÇZÇZƊ⁾ULXȮOịØ.¤?F⁻Ṣ$$¿,“”Ṫ

Try it online!

Full program. Outputs moves to STDOUT using L for left and R for right. Keeps trying random moves until the matrix is sorted, so not very efficient in terms of speed or algorithmic complexity.

JavaScript (ES6),  226  219 bytes

Brute force search, using right ("R") and down ("D") moves.

Returns either a string describing the moves, or an empty array if the input matrix is already sorted. Columns and rows in the output are 0-indexed.

f=(m,M=2)=>(g=(s,m)=>m[S='some'](p=r=>r[S](x=>p>(p=x)))?!s[M]&&m[0][S]((_,x,a)=>g(s+'D'+x,m.map(([...r],y)=>(r[x]=(m[y+1]||a)[x])&&r)))|m[S]((_,y)=>g(s+'R'+y,m.map(([...r])=>y--?r:[r.pop(),...r]))):o=s)([],m)?o:f(m,M+2)

Try it online!

Commented

f =                              // f = main recursive function taking:
(m, M = 2) => (                  //   m[] = input matrix; M = maximum length of the solution
  g =                            // g = recursive solver taking:
  (s, m) =>                      //   s = solution, m[] = current matrix
    m[S = 'some'](p =            // we first test whether m[] is sorted
      r =>                       // by iterating on each row
        r[S](x =>                // and each column
          p > (p = x)            // and comparing each cell x with the previous cell p
        )                        //
    ) ?                          // if the matrix is not sorted:
      !s[M] &&                   //   if we haven't reached the maximum length:
      m[0][S]((_, x, a) =>       //     try all 'down' moves:
        g(                       //       do a recursive call:
          s + 'D' + x,           //         append the move to s
          m.map(([...r], y) =>   //         for each row r[] at position y:
            (r[x] =              //           rotate the column x by replacing r[x] with
              (m[y + 1] || a)[x] //           m[y + 1][x] or a[x] for the last row (a = m[0])
            ) && r               //           yield the updated row
      ))) |                      //
      m[S]((_, y) =>             //     try all 'right' moves:
        g(                       //       do a recursive call:
          s + 'R' + y,           //         append the move to s
          m.map(([...r]) =>      //         for each row:
            y-- ?                //           if this is not the row we're looking for:
              r                  //             leave it unchanged
            :                    //           else:
              [r.pop(), ...r]    //             rotate it to the right
      )))                        //
    :                            // else (the matrix is sorted):
      o = s                      //   store the solution in o
)([], m) ?                       // initial call to g(); if we have a solution:
  o                              //   return it
:                                // else:
  f(m, M + 2)                    //   try again with a larger maximum length