Solution:

Set $M + 1213 = y^2$ and $M + 3773 = x^2.$ Subtracting, $x^2 - y^2 = 2560,$ so $(x - y)(x + y) = 2560.$ The two factors share a parity, and their product is even, so both are even: write $x - y = 2s,$ $x + y = 2t,$ with $st = 640.$ To make $M$ as large as possible we want $y = t - s$ as large as possible, so $s$ as small as possible. Take $s = 1, t = 640,$ giving $y = 639.$ Then $M = 639^2 - 1213 = 407108,$ whose units digit is $8.$ Thus, E is the correct answer.