if and only if $G$ is connected and regular.
To prove the "only if", assume $J$ is a polynomial in $A$. Then $JA=AJ$. The entries in the $i$th row of $AJ$ are all equal to the sum of the entries in the $i$th row of $A$. The entries in the $i$th column of $JA$ are all equal to the sum of the entries in the $i$th column of $A$. Therefore, the sums of entries in a row of $A$ is constant. This shows that $G$ is regular. Also $G$ must be connected, for otherwise $i$ and $j$ is not connected and the $ij$th entry of $A^n$ is always zero and $J$ cannot be a polynomial in $A$.
But how can I show the other implication?