Matrix rotation sort
JavaScript (ES6),  226  219 bytes
Brute force search, using right (&quot;R&quot;) and down (&quot;D&quot;) 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)=&gt;(g=(s,m)=&gt;m[S='some'](p=r=&gt;r[S](x=&gt;p&gt;(p=x)))?!s[M]&amp;&amp;m[0][S]((_,x,a)=&gt;g(s+'D'+x,m.map(([...r],y)=&gt;(r[x]=(m[y+1]||a)[x])&amp;&amp;r)))|m[S]((_,y)=&gt;g(s+'R'+y,m.map(([...r])=&gt;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) =&gt; (                  //   m[] = input matrix; M = maximum length of the solution
  g =                            // g = recursive solver taking:
  (s, m) =&gt;                      //   s = solution, m[] = current matrix
    m[S = 'some'](p =            // we first test whether m[] is sorted
      r =&gt;                       // by iterating on each row
        r[S](x =&gt;                // and each column
          p &gt; (p = x)            // and comparing each cell x with the previous cell p
        )                        //
    ) ?                          // if the matrix is not sorted:
      !s[M] &amp;&amp;                   //   if we haven't reached the maximum length:
      m[0][S]((_, x, a) =&gt;       //     try all 'down' moves:
        g(                       //       do a recursive call:
          s + 'D' + x,           //         append the move to s
          m.map(([...r], y) =&gt;   //         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])
            ) &amp;&amp; r               //           yield the updated row
      ))) |                      //
      m[S]((_, y) =&gt;             //     try all 'right' moves:
        g(                       //       do a recursive call:
          s + 'R' + y,           //         append the move to s
          m.map(([...r]) =&gt;      //         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