With m=n and k=2 a brute force search gives the sequence of feasible/total for m=1,... as
2/2, 14/16, 108/512, 1256/65536, ...
which is not on oeis even after dividing by two to account for the label symmetry.

Edit:
Removing single-color configurations and dividing by two gives
http://oeis.org/A068416
which I believe corresponds to m=n, k=2 for your original question.