Constructions for $n=3$ and $n=5$ are easy. For $n>5$, color the odd rows black and the even rows white. If the squares can be paired in the way desired, each pair we choose must have one black cell and one white cell, so the numbers of black cells and white cells are the same. The number of black cells is $\frac{n+1}{2}n-4$ or $\frac{n+1}{2}n-5$ depending on whether the removed center cell is in an odd row. The number of white cells is $\frac{n-1}{2}n$ or $\frac{n-1}{2}n-1$. But $\left(\frac{n+1}{2}n-5\right)-\frac{n-1}{2}n=n-5$ so for $n>5$ this pairing is impossible. Thus the answer is $n=3$ and $n=5$.