For both a) and b) it is obvious that $n$ has to be odd and greater than $k$.

a) Hence, $n$ is odd and greater than $4$. Let us show that any such odd $n$ satisfies the condition. It is clear that any stripe $4 \times l$ can be covered by rectangles $4 \times 1$. For $5 \times 5$ and $7 \times 7$ the required coverage is shown on Fig. 7–8. For any odd $n = 4m + 5$ and $n = 4m + 7$ it is sufficient to cut the square $n \times n$ into a square $5 \times 5$ or $7 \times 7$ and several stripes $4 \times l$ (Fig. 9).

Fig. 9

b) Let us show that by a similar scheme we can cover squares $n = 8m + 9$ and $n = 8m + 15$. For this, it is sufficient to cover $9 \times 9$ and $15 \times 15$. Then, each $n \times n$ of the above size can be cut into a square $9 \times 9$ or $15 \times 15$ and several stripes $8 \times l$ (Fig. 10–11).

Now, let us show that squares $n = 8m + 11$ and $n = 8m + 13$ cannot be covered according to the condition. For the square $11 \times 11$, consider this coloring in black and white squares, as shown in Fig. 12. Out of $121$ squares, $65$ are black and $56$ are white, which means there are $9$ more black cells than white ones. Each rectangle $8 \times 1$ inside of this square covers the same number of black and white cells. Therefore, if there existed such coverage, the number of black and white cells would differ only by $1$. For the general case square $n \times n$ when $n = 8m + 11$, analogous coloring yields $9$ more black cells than white cells.

Fig. 10

Analogously, for square $13 \times 13$, we show the coloring (Fig. 13) with $89$ black and $80$ white cells, which again means there is no such coverage. And for the case $n \times n$ when $n = 8m + 13$, the same holds.