Notably, this demonstrates the importance of the puzzle's specification that each square of the k-by-1 tiles must align with a chessboard square. Suppose, for example, k=5 and n=4, it is possible to place a 5-by-1 tile diagonally in a 4-by-4 square. This will leave 11 free squares, which is not a perfect square.
Tile the entire rectangle from position (r,0) to position (n-1,n-1) by horizontal tiles, and the entire rectangle from (0,r-1) to (r-1,n-1) by vertical tiles. This leaves untiled the square between (0,0) and (r-1,r-1). I claim that if we are able to tile the board, leaving only a square of width at most k/2 untiled, then this is the optimal tiling.
To prove this claim, let us color each of the chessboard's squares. We will color (x,y) by a color corresponding to (x+y) mod k. Note that in this coloring, every k-by-1 tile covers exactly one square of each of the k colors.
Consider, however, the colors of the untiled r-by-r square. Its (0,0) corner gets the 0 color, and the colors advance up until its (r-1,r-1) color gets the color corresponding to 2r-2. This is, by assumption, smaller than k, so still unaffected by the modulo. In fact, 2r-1 is also smaller than k, so the entire untiled area does not include any square of the color corresponding to 2r-1.
We've demonstrated this for a square with one corner at (0,0), but the principle is sound regardless of where the square is. If this is the only square left untiled, this means that the number of k-by-1 tiles used was exactly enough to exhaust all of the chessboard's squares colored by some specific color. Therefore, no arrangement of the tiles can be made to use more k-by-1 polyominoes. Therefore, m=r2 is the optimum. Here, too, the optimum is a perfect square.
We use the method of Case 2 to reduce to a (k+r)-by-(k+r) square. Now, let us tile the remaining square in the way demonstrated below.
The untiled portion left in the center has a square shape, and its width is k-r<k-k/2=k/2. By the claim proved in Case 2, this is, once again, the optimal tiling, leaving m=(k-r)2 squares untiled. Once again, m is a perfect square.
Q.E.D.