Suppose $M + 1213 = j^2$ and $M + 3773 = k^2$ for nonnegative integers $j$ and $k$. Then
$$(k + j)(k - j) = k^2 - j^2 = 3773 - 1213 = 2560 = 5 \cdot 2^9.$$
Because $k + j$ and $k - j$ have the same parity and their product is even, they must both be even, and it follows that one of them is $5 \cdot 2^i$ and the other is $2^{9-i}$ for some $i$ with $1 \le i \le 8$. Solving for $k$ gives
$$k = \frac{5 \cdot 2^i + 2^{9-i}}{2}.$$
To maximize $M$ it is sufficient to maximize $k$, and this will occur when $i = 8$ and $k = 5 \cdot 2^7 + 1 = 641$. Therefore $M = 641^2 - 3773$, and its units digit is 8.

Because $(n + 1)^2 - n^2 = 2n + 1$, successive terms in the sequence of squares, 1, 4, 9, 16, ..., differ by successive odd numbers; and because $(n + 2)^2 - n^2 = 4(n + 1)$, the terms in this sequence that are two apart differ by successive multiples of 4. The two squares required in this problem differ by $3773 - 1213 = 2560$, a multiple of 4. It follows that the greatest such squares are two apart in the sequence of squares, so $n + 1 = \frac{2560}{4} = 640$. Therefore these squares are $n^2 = 639^2$ and $(n + 2)^2 = 641^2$, and $M + 1213 = 639^2$. Then $M = 639^2 - 1213$, and its units digit is 8.

Because $(n + 1)^2 - n^2 = 2n + 1$, successive terms in the sequence of squares, $1, 4, 9, 16, \ldots$, differ by successive odd numbers; and because $(n + 2)^2 - n^2 = 4(n + 1)$, the terms in this sequence that are two apart differ by successive multiples of 4. The two squares required in this problem differ by $3773 - 1213 = 2560$, a multiple of 4. It follows that the greatest such squares are two apart in the sequence of squares, so $n + 1 = \frac{2560}{4} = 640$. Therefore these squares are $n^2 = 639^2$ and $(n + 2)^2 = 641^2$, and $M + 1213 = 639^2$. Then $M = 639^2 - 1213$, and its units digit is 8.