Counting grid colorings that avoid certain features
If you want bounds for a fixed $k$ (rather than an asymptotic expression/formula that works for all $k$), one approach might be to use random sampling: repeatedly choose a random coloring, check whether it meets your criteria, and count how many of the trials were successful.  This gives you an estimate of the fraction of colorings that meet your criteria.  This can be converted into a rough estimate of the total number of colors that meet your criteria (just multiply by $k^{mn}$).

You can then use a Chernoff bound to get upper and lower bounds on the number of colorings that meet your criteria, where these bounds hold with probability $\ge 1-2^{-100}$ (taken over the random trials).  In other words, you would have to be extremely unlucky in your choice of random trials for those bounds to be wrong.