Identify the smallest possible tile in the matrix
JavaScript (ES6),  354 352 345  342 bytes
I/O: matrix of integers.
This is quite long but pretty fast -- at least with those test cases.

m=&gt;m[b=P='map']((r,h)=&gt;r[P]((_,w)=&gt;(M=m.slice(~h)[P](r=&gt;r.slice(~w)),a=~w*~h,g=(x,y,F)=&gt;a&gt;b|q.some((r,Y)=&gt;r.some((v,X)=&gt;~v?v^m[Y][X]:![x=X,y=Y]))?0:1/y?[...P+0][P](z=&gt;(F=k=&gt;!M[P]((r,Y)=&gt;r[P]((v,X)=&gt;k^1?q[y-Y][x-X]=v|k:(z|=~(q[y-X]||0)[x-Y],T[X]=T[X]||[])[Y]=v),T=[]))(1)&amp;T.reverse(M=T)|z||g(F())|F(-1)):(o=M,b=a))(q=m[P](r=&gt;r[P](_=&gt;-1)))))&amp;&amp;o

Try it online!
How?
Whatever the tiling is, it is guaranteed that each corner of the matrix is also a corner of the tile that we're looking for. The two outer map() loops extract each possible tile \$M\$ from the bottom-right side of the input matrix \$m\$ and compute its area \$a\$.
m.map((r, h) =&gt;           // for each row r[] at position h in m[]:
  r.map((_, w) =&gt;         //   for each value at position w in r[]:
    (                     //
      M =                 //     build M[]:
        m.slice(~h)       //       keep the last h + 1 rows of m[]
        .map(r =&gt;         //       for each of them:
          r.slice(~w)     //         keep the last w + 1 columns
        ),                //
      a = ~w * ~h,        //     area = (w + 1) * (h + 1)
      ...                 //     attempt to do a tiling with M
    )                     //
  )                       //   end of map()
)                         // end of map()

We build a matrix \$q\$ with the same dimensions as \$m\$, initially filled with \$-1\$.
q = m.map(r =&gt; r.map(_ =&gt; -1))

At each iteration of the recursive function \$g\$, we look for the position \$(x,y)\$ of the last cell in \$q\$ still set to \$-1\$, going from left to right and from top to bottom.
By definition, this cell has either a cell already set or a border on its right, and ditto below it. So it must be the bottom-right corner of a new tile, such as the cell marked with an 'x' below:

Simultaneously, we test whether there's a cell in \$q\$ whose value is not \$-1\$ and is different from the value in \$m\$ at the same position. If such a tile is found, we abort the recursion.
q.some((r, Y) =&gt;          // for each row r[] at position Y in q[]:
  r.some((v, X) =&gt;        //   for each value v at position X in r[]:
    ~v ?                  //     if v is not equal to -1:
      v ^ m[Y][X]         //       abort if v is not equal to M[Y][X]
    :                     //     else:
      ![x = X, y = Y]     //       set (x, y) = (X, Y)
  )                       //   end of some()
)                         // end of some()

If all cells of \$q\$ are matching the cells of \$m\$ and the area of \$M\$ is less than (or equal to) the best area found so far, we update the output \$o\$ to \$M\$.
Otherwise, we invoke the following code 4 times:
F(1) &amp; T.reverse(M = T) | z || g(F()) | F(-1)

The behavior of the helper function \$F\$ depends on the parameter \$k\$:

If \$k=1\$, it computes the transpose \$T\$ of \$M\$ and checks whether all cells in \$q\$ between \$(x-w,y-h)\$ and \$(x,y)\$ are set to \$-1\$. The result of this test is saved in \$z\$.
If \$k\$ is undefined, it copies the content of \$M\$ to \$q\$ at \$(x-w,y-h)\$.
If \$k=-1\$, it cancels the previous operation by restoring all updated values to \$-1\$.

It is defined as follows:
F = k =&gt;                  // k = parameter
  !M.map((r, Y) =&gt;        // for each row r[] at position Y in M[]:
    r.map((v, X) =&gt;       //   for each value v at position X in r[]:
      k ^ 1 ?             //     if k is not equal to 1:
        q[y - Y][x - X] = //       set q[y - Y][x - X]
          v | k           //       to v if k is undefined, or -1 if k = -1
      :                   //     else:
        ( z |=            //       update z:
            ~( q[y - X]   //         read q at (x - Y, y - X)
              || 0        //
            )[x - Y],     //         set z if it's not equal to -1
          T[X] =          //       compute T by writing v at the
            T[X] || []    //       relevant position
        )[Y] = v          //
    ),                    //   end of inner map()
    T = []                //   initialize T to an empty array
  )                       // end of outer map()

Therefore, the code block mentioned above can be interpreted as follows:
F(1)                      // compute the transpose T[] of M[] and test whether
&amp;                         // M[] can be copied at (x-w, y-h) in q[]
T.reverse(M = T)          // reverse T[] and assign it to M[], which means
|                         // that M[] has been rotated 90° counterclockwise
z ||                      // if z = 0:
  g(F()) |                //   copy M[] to q[] and do a recursive call
  F(-1)                   //   restore q[] to its previous state