$k=3$ and $k=5$ are certainly possible, and I believe the procedure for $k=5$ can be extended to other odd $k$ as well. Here is a picture of $k=3$:

_{(click to enlarge; Java source code to generate this SVG file is here on GitHub)}

_{(click to enlarge; Java source code to generate this SVG file is here on GitHub)}

The procedure for $k=3$ is as follows: divide the board into 3-by-3 boxes, centered around the removed squares. There are eight ways for the knight to enter a box, and once it's in, it will make a complete tour in the box and end on one of the two other squares a knight's move away, so there are 16 possibilities labelled 0 through F:

(green = starting square, red = finishing square)

From one box, it can then jump to another box. The idea is to make a spiral of these boxes, centered at the origin. Therefore, we need to figure out for each box which other boxes can be next, depending on which direction we want to go. For example, from box 0 (and box D), we can't go left (we would end up in the box itself), we can go up to box A or B, down to box 2 or 3 and right to boxes 2, 3, A and B. The table is as follows:

Note that it's possible to go right by alternating between E and C, go down by F and 1, go left by 5 and 3 and go up by 9 and 7. This is the key to fill the spiral, which will look like this:

(For the first image, I ended up with C and F instead of 0 and 2 in the center.)

Since the length of the spiral's horizontal sides are always even, and odd for the vertical sides, this pattern can be extended indefinitely.

For $k \ge 5$, it makes more sense to leave the removed square in the corner. I had a computer program (linked above) brute-force all possible knights tours inside a $k$ by $k$ box with the top left square removed; then, it's a matter of finding the right 'connections' between the boxes like I did for the $k=3$ case.