M={{-4, -4, -2 - 2 (c - d), 3 + c - 2 d, 2 + 2 c, -3 - c + d, 2 - 2 c,4 - d},
      {4, -4, -4, 0, 4, 0, 0, 0}, {6 + 2 (c - d), 4, -4, -8,4 + 2 (2 - 2 c), 2 (2 + 2 c), -8, 2 (4 + 2 d)},
      {-3 - c + 2 d, 4,12, -4, -6 + 2 c, -2 - 2 c - d,4 + 2 (2 + d), -12 - 5 d},
      {-2 - 2 c, -4, -4 - 2 (2 - 2 c),10 - 2 c, -4, 2 + 2 (1 + d), -4 (2 + d), 2 (4 + 2 d)},
      {3 + c - d,0, -2 (2 + 2 c), 2 + 2 c + d, 2 - 2 (1 + d), -4, 2 (2 + d),4 - d},
      {-2 + 2 c, 0, 8, -4 - 2 (2 + d), 4 (2 + d),4 - 2 (2 + d), -4, -8},
      {-4 + d, 0, -2 (4 + 2 d),12 + 5 d, -2 (4 + 2 d), -4 + d, 12, -4}};
Solve[Map[If[IntegerQ[#],Nothing,#==0]&,Flatten[M]],{c,d},Modulus->4]

Eliminate the lone constants and leave the variable expressions and solve mod 4

which in an instant gives

{{c->1,d->0}}

Then

Map[If[IntegerQ[#],Nothing,Mod[#/.{c->1,d->0},4]==0]&,Flatten[M]]

in an instant gives

{True,True,True,True,True,True,True,True,True,
 True,True,True,True,True,True,True,True,True,
 True,True,True,True,True,True,True,True,True,
 True,True,True,True,True,True,True,True,True}

How to solve a Matrix of congruences?

For example, I have

M={{-4, -4, -2 - 2 (c - d), 3 + c - 2 d, 2 + 2 c, -3 - c + d, 2 - 2 c, 
  4 - d}, {4, -4, -4, 0, 4, 0, 0, 0}, {6 + 2 (c - d), 4, -4, -8, 
  4 + 2 (2 - 2 c), 2 (2 + 2 c), -8, 2 (4 + 2 d)}, {-3 - c + 2 d, 4, 
  12, -4, -6 + 2 c, -2 - 2 c - d, 
  4 + 2 (2 + d), -12 - 5 d}, {-2 - 2 c, -4, -4 - 2 (2 - 2 c), 
  10 - 2 c, -4, 2 + 2 (1 + d), -4 (2 + d), 2 (4 + 2 d)}, {3 + c - d, 
  0, -2 (2 + 2 c), 2 + 2 c + d, 2 - 2 (1 + d), -4, 2 (2 + d), 
  4 - d}, {-2 + 2 c, 0, 8, -4 - 2 (2 + d), 4 (2 + d), 
  4 - 2 (2 + d), -4, -8}, {-4 + d, 0, -2 (4 + 2 d), 
  12 + 5 d, -2 (4 + 2 d), -4 + d, 12, -4}}

where each entry must be congruent to 0 mod 4. I know the solution to be

$d\equiv_4 0,2$

and $c\equiv_4\pm 1$,

but trying to solve with the method I have described in my original post returns the empty set.