If $A^k$ commutes with $B$ then $A$ commutes with $B$.

Hint. Try to prove that $A$ is a polynomial in $A^k$.

Edit. To prove the hint, you may follow darij grinberg's comment below. I did essentially the same thing, but from a matrix analytic rather than linear algebraic perspective: I considered the primary matrix function $f(X)=(I+X)^{1/k}=\sum_{i=0}^\infty \frac{f^{(i)}(0)}{k!}X^i$ for a nilpotent matrix $X$ associated with the scalar function $f(x)=(1+x)^{1/k}$. Put $X=A^k-I$ and we are done.

Alternatively, the hint can be proved using only Jordan forms, but the argument is much longer.

1. Let $J$ be the Jordan form of $A$. Since all eigenvalues of $A$ are ones, we may write $J=J_{m_1}\oplus J_{m_2}\oplus\cdots\oplus J_{m_b}$, where $1\le m_1\le m_2\le\cdots\le m_b$ and $J_m$ denotes a Jordan block of size $m$ for the eigenvalue $1$.
2. Note that if $r\ge0$ and $m<n$, then $J_m^r$ coincides with the leading principal $m\times m$ submatrix of $J_n^r$. Hence $p(J_m^k)$ coincides with a leading principal submatrix of $p(J_n^k)$ for any polynomial $p$.
3. It follows that if $p(J_n^k)=J_n$, then $p(J_m^k)=J_m$ for every $m<n$. This is true in particular when $m\in\{m_1,m_2,\ldots,m_b\}$. Consequently, $p(A^k)=A$.
4. Hence the problem boils down to finding a polynomial $p$ such that $p(J_n^k)=J_n$. This should be straightforward and I will leave it to you.