Two dimensional linear recurrences are a bit more complex algebraically.
The concept corresponding to the linear complexity would in some sense be the degree $(n,m)$ of the minimal degree generating polynomial of the form
$$
x^{n}y^m- \sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} x^i y^j
$$
which would correspond to the 2D linear recurrence
$$
s_{t+n,t'+m}=\sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} s_{t+i,t'+j}
$$
where $t,t'$ are the indices in the two dimensions.
Sakata has generalised the Berlekamp Massey algorithm (BMA) to 2, and then to N dimensions; See here (seems to be publicly available). From the abstract:
We present an algorithm for finding a minimal set of two-dimensional linear recurring relations capable of generating a prescribed finite two-dimensional array. This is a two-dimensional extension of the Berlekamp-Massey algorithm for synthesizing a shortest linear feedback shift-register capable of generating a given finite sequence. The complexity of computation for an array of size $n$ is $O(n^2)$ under some reasonable assumptions. Furthermore, we make clear some relationship between our algorithm and Gröbner bases of bivariate polynomial ideals, where polynomials correspond one-to-one to linear recurring relations.
The reason they are complex is that (up to some handwaving) for a finite field $\mathbb{F}$ the one variable polynomial ring $\mathbb{F}[x]$ all ideals are principal (have a single polynomial generator). So for the BMA to work it is sufficient to find one generator of minimum degree. In multiple variables, not all ideals of $\mathbb{F}[x_1,\ldots,x_n]$ are principal.
The definition of two variable degree and the ordering of degrees of terms is another issue, but that can be done via lexicographic ordering for example.
