We show that the necessary and sufficient condition of the problem is $N$ is divisible by $M$.

The sufficient condition is easy. If $N$ is divisible by $M$ then $N/M = d$ is a positive integer. In this case, we can divide the $N \times N$ table into $Nd$ rectangles of size $M \times 1$. We can easily turn on all of the lights in such a way that turn on one $M \times 1$ rectangle at the time.

Now we show that $N$ is divisible by $M$ is also the necessary condition. We color unit squares of the table by $M$ colors, denoted by $0$ to $M-1$ such that the square $(i, j)$ is colored by the color $i + j - 2 \pmod M$. A light on the $s$-colored square is called a $s$-light.

We have the following observation: At each step of implementation, we will change the status of exactly $M$ lights, one light in each color. Since all the lights are initially off so after each step, the total lights are switched on of each color are of the same parity. So in order to switch on all the lights, the numbers of lights of each colors must have the same parity. Suppose that $N$ is not divisible by $M$, then $N = Mk + r$ ($1 \le r \le M-1$). We divide the table $N \times N$ into four subtables: $Mk \times Mk$, $Mk \times r$, $r \times Mk$, $r \times r$.

1) Each of $Mk \times Mk$, $Mk \times r$, $r \times Mk$ is a union of $M \times 1$ rectangles or $1 \times M$ rectangles so the number of lights of each color is $Mk^2 + 2kr$.

2) In the table $r \times r$, the number of $(r-1)$-lights is $r$, and the number of $r$-lights is $r-1$. Indeed, because $r \le M-1$ then any row contains the light with distinct color. On the other hand, the $(r-1)$-lights appear in all the rows of subtable and the $r$-light appears in all the rows of subtable except the first row, then the proof of this case follows.

From 1) and 2), the number of $r$-lights and the number of $(r-1)$-lights have different parity, which is a contradiction, then we have completed the problem.