Does $A^n$ is unitary imply that $A$ is unitary?

In general, the answer is no. In fact, I can prove

For any $n\leq k$ there is a $k\times k$ matrix $A$ for which $A^n = I$ is unitary but $A, A^2 ,...A^{n-1}$ are not.

I don't know what happens if $n > k$, but certainly my approach fails.

Here's the proof. First note that $A$ satisfies the $n=k$ case, then the block diagonal matrix $\operatorname{diag}(A,1,1,1,1..,1)$ satisfies the $n,k$ case with $k > n$. So we may assume wlog that $k = n$.

Now, on $\mathbb{C}^n$, consider the standard basis $\{e_i\}$. Let $A$ be the linear operator defined by $Ae_1 = 2e_2$, $Ae_2 = \frac{1}{2} e_3$, and $Ae_{m} = e_{m+1}$ for all other $m$ including $Ae_{n} = e_1$.

No power $A, A^2, ..., A^{n-1}$ is unitary. To see this, note that for $0<k<n$, $A^{k}e_{n-k+2} = 2e_2$, so doubles the length of this vector.

On the other hand, $A^n$ applied to $e_i$ is itself, so $A^n$ is the identity as claimed.

(Concretely, this gives the matrices $A = \begin{bmatrix} 0 & 2\\ \frac{1}{2} & 0\end{bmatrix}$, $A = \begin{bmatrix} 0 & 2 & 0 \\ 0& 0&\frac{1}{2}\\ 1 & 0 & 0\end{bmatrix}$, $A = \begin{bmatrix} 0 & 2 & 0 & 0\\ 0& 0& \frac{1}{2} & 0\\ 0& 0& 0& 1\\ 1&0&0&0\end{bmatrix}$ and the pattern continues by sticking more $1$s in the upper off diagonal places.)