After $i$ steps, there will be $k - 2i$ heaps left on the table; thus if a single heap is to remain in the end, the number $k$ must be odd and the total number of steps has to be $\frac{1}{2}(k-1)$. Let us distinguish two cases, according as the remainder of $k$ upon division by 4 is 1 or 3.

The case of $k = 4c + 1$. In the beginning there are $1 + \dots + k = \frac{1}{2}k(k+1) = (4c+1)(2c+1)$ stones on the table, from which in course of the $2c$ steps we will remove $1 + \dots + 2c = c(2c+1)$ stones; thus the number of stones in the last heap will be
$$p = (4c+1)(2c+1) - c(2c+1) = (2c+1)(3c+1).$$
Since the numbers $2c+1$ and $3c+1$ are coprime, $p$ is a perfect square if and only if both $2c+1$ and $3c+1$ are perfect squares; that is, if and only if their quadruples $4(2c+1) = 2k+2$ and $4(3c+1) = 3k+1$ are perfect squares.

The case of $k = 4c + 3$. In the beginning there are $1 + \dots + k = \frac{1}{2}k(k+1) = 2(c+1)(4c+3)$ stones on the table, from which we remove in course of all the $2c + 1$ steps a total of $1 + \cdots + (2c + 1) = (c + 1)(2c + 1)$ stones; thus the last single heap will contain
$$p = 2(c+1)(4c+3) - (c+1)(2c+1) = (c+1)(6c+5).$$
If $p$ were a perfect square, then so would have to be the two coprime numbers $c+1$ and $6c+5$. Let us show that this is not possible. Assume that there exist natural numbers $x, y$ such that $c+1 = x^2$ and $6c+5 = y^2$. From the equality $6x^2 - y^2 = 1$ it follows that the number $y$ is odd, hence $y^2$ gives a remainder of 1 upon division by 8. The number $6x^2$ then gives the remainder of 2, which implies that $3x^2$ gives remainder 1 upon division by 4 — a contradiction. Hence in the case of $k = 4c+3$ the number $p$ is never a perfect square, and likewise the number $3k+1 = 12c+10$ is never a perfect square (being an even number not divisible by 4).

Let us finally find the least number $k = 4c+1$, $c \ge 1$, for which both numbers $2c+1$ and $3c+1$ are perfect squares. From the equalities $2c+1 = x^2$ and $3c+1 = y^2$ for suitable integers $x, y > 1$ it follows that $3x^2 - 2y^2 = 1$, whence $x$ is odd, but then the number $2y^2$ gives remainder 2 upon division by 4, so $y$ is also odd. Set $x = 2a+1$, $y = 2b+1$ ($a, b > 0$ integer) and substitute this into the equality $3x^2 - 2y^2 = 1$; upon a small manipulation this leads to the relation $3a(a+1) = 2b(b+1)$, and taking successively $a = 1, 2, \dots$ we soon find the smallest solution $a = 4$ and $b = 5$, corresponding to $x = 9, y = 11, c = 40$ and $k = 161$.