No, the converse of Cayley-Hamilton is not true for $n\times n$ matrices with $n\gt 1$; in particular, it fails for $2\times 2$ matrices.
For a simple counterexample, notice that if $p(A)=0$, then for every multiple $q(x)$ of $p(x)$ you also have $q(A)=0$; so you would want to amend the converse to say "if $p(A)=0$, then $p(a)$ is a multiple of the characteristic polynomial of $A$". But even that amended version is false
However, the only failure in the $2\times 2$ matrix case are the scalar multiples of the identity. If $A=\lambda I$, then $p(x)=x-\lambda$ satisfies $p(A)=0$, but the characteristic polynomial is $(x-\lambda)^2$, not $p(x)$.
For bigger matrices, there are other situations where even this weakened converse fails.
The concept that captures the "converse" of Cayley-Hamilton is the minimal polynommial of the matrix, which is the monic polynomial $p(x)$ of smallest degree such that $p(A)=0$. It is then easy to show (using the division algorithm) that if $q(x)$ is any polynomial for which $q(A)=0$, then $p(x)|q(x)$. (Be careful to justify that if $m(x)=r(x)s(x)$, then $m(A)=r(A)s(A)$; this is not immediate because matrix multiplication is not in general commutative!) So we have:
Theorem. Let $A$ be an $n\times n$ matrix over $\mathbf{F}$, and let $\mu(x)$ be the minimal polynomial of $A$. If $p(x)\in \mathbf{F}[x]$ is any polynomial such that $p(A)=0$, then $\mu(x)$ divides $p(x)$.
The Cayley-Hamilton Theorem shows that the characteristic polynomial is always a multiple of the minimal polynomial. In fact, one can prove that every irreducible factor of the characteristic polynomial must divide the minimal polynomial. Thus, for a $2\times 2$ matrix, if the characteristic polynomial splits and has distinct roots, then the characteristic and minimal polynomial are equal. If the characteristic polynomial is irreducible quadratic and we are working over $\mathbb{R}$, then again the minimal and characteristic polynomials are equal. But if the characteristic polynomial is of the form $(x-a)^2$, then the minimal polynomial is either $(x-a)$ (when the matrix equals $aI$), or $(x-a)^2$ (when the matrix is not diagonalizable).
As for solving this problem: if $\lambda$ is an eigenvalue of $A$, and $A$ is invertible, then $\lambda\neq 0$, and $\frac{1}{\lambda}$ is an eigenvalue of $A^{-1}$: for if $\mathbf{x}\neq\mathbf{0}$ is such that $A\mathbf{x}=\lambda\mathbf{x}$, then multiplying both sides by $A^{-1}$ we get $\mathbf{x} = A^{-1}(\lambda \mathbf{x}) = \lambda A^{-1}\mathbf{x}$. Dividing through by $\lambda$ shows $\mathbf{x}$ is an eigenvector of $A^{-1}$ corresponding to $\frac{1}{\lambda}$.
Since $A=A^{-1}$, that means that if $\lambda_1,\lambda_2$ are the eigenvalues of $A$, then $\lambda_1 = \frac{1}{\lambda_1}$ and $\lambda_2=\frac{1}{\lambda_1}$; thus, each eigenvalue is either $1$ or $-1$.
If the matrix is diagonalizable, then we cannot have both equal to $1$ (since then $A=I$), and they cannot both be equal to $-1$ (since $A\neq -I$), so one eigenvalue is $1$ and the other is $-1$. Since the trace of a square matrix equals the sum of its eigenvalues, the sum of the eigenvalues is $0$.
Why is $A$ diagonalizable? If it has two distinct eigenvalues, $1$ and $-1$, then there is nothing to do; we know it is diagonalizable. If it has a repeated eigenvalue, say $1$, but $A-I$ is not the zero matrix, pick $\mathbf{x}\in \mathbb{R}^2$ such that $A\mathbf{x}\neq \mathbf{x}$; then $$\mathbf{0}=(A-I)^2\mathbf{x} = (A^2-2A + I)\mathbf{x} = (2I-2A)\mathbf{x}$$
by the Cayley Hamilton Theorem. But that means that $2(A-I)\mathbf{x}=\mathbf{0}$, contradicting our choice of $\mathbf{x}$. Thus, $A-I=0$, so $A=I$ and $A$ is diagonalizable. A similar argument shows that if $-1$ is the only eigenvalue, then $A+I=0$.
.
(Hiding behind that paragraph is the fact that if the minimal polynomial is squarefree and splits, then the matrix is diagonalizable; since $p(x)=x^2-1=(x-1)(x+1)$ is a multiple of the minimal polynomial, the matrix must be diagonalizable).
So this completes the proof that the trace must be $0$, given that $A\neq I$ and $A\neq -I$.
Best Answer
You are reading too much into the question. The result does not generalise well to higher dimensions. Let us consider the $2\times2$ case first. Presumably $A$ is real. Let $d=|\det(A)|$, the absolute value of $\det(A)$. The given condition can be rewritten as $\det(A + d^2A^{-1}) = 0$, which implies that $\det(A^2 + d^2 I) = 0$. This simply means that $-d^2$ is a negative eigenvalue of $A^2$.
Since $\det(A^2)=d^2$, when $A$ is $2\times2$, the other eigenvalue of $A^2$ has to be $-1$. Thus $A^2$ has two negative real eigenvalues $-d^2$ and $-1$. Therefore $A$ must have a conjugate pair of eigenvalues. Hence $d=1$ and also $\det(A)=|\det(A)|$. It follows that the characteristic polynomial of $A^2$ is $p(x) = (x+d^2)(x+1) = (x+1)^2$ and $$ \det\left(A - \det(A)\operatorname{adj}(A)\right) =\det(A^{-1})\det(A^2 - d^2I) =\frac1d p(d^2) = 4. $$ This concludes the $2\times2$ case. When $A$ is at least $3\times3$, only what we've said in the first paragraph remains valid. The condition $\det\left(A + \det(A)\operatorname{adj}(A)\right)$ is true if and only if $-d^2$ is an eigenvalue of $A^2$, meaning that $A$ is similar to $$ \left(\begin{array}{c|c}\pmatrix{0&-d\\ d&0}&\ast\\ \hline0&P^{-1}\end{array}\right) $$ for some real matrix $P$ with determinant $\pm d$ (unlike the $2\times2$ case, $\det(A)$ is not necessarily equal to $|\det(A)|$ here and its sign is controlled by $P$). Therefore \begin{align} \det\left(A - \det(A)\operatorname{adj}(A)\right) &=\det(A-d^2A^{-1})\\ &=4d^2\det\left(P^{-1} - d^2P\right)\\ &=4\det(P)\det\left(I - d^2P^2\right), \end{align} whose value can assume any positive, zero or negative real value. The answer by loup blanc is obtained by using a block-diagonal matrix $A$ with $d=P=\frac1z$.