We show first that if $A$ is a matrix from $M_n(\mathbb{R})$ such that $A^2 + I_n$ is singular, then there exists a matrix $B$ in $M_n(\mathbb{R})$, such that $AB = -BA$.
As $A^2 + I_n$ is singular, $i$ is a proper value of $A$, and $-i$ is a proper value of the transpose $A^\tau$. There exist two proper vectors $\mathbf{x}$ and $\mathbf{y}$ in $M_{n,1}(\mathbb{C})$, so that $A\mathbf{x} = i\mathbf{x}$ and $A^\tau\mathbf{y} = -i\mathbf{y}$. Because $\mathbf{x}$ and $\mathbf{y}$ are nonzero, $B = \mathbf{x}\mathbf{y}^\tau$ is a nonzero matrix in $M_n(\mathbb{C})$.
The following relations show that $A$ and $B$ anticommute:
$$AB = A\mathbf{x}\mathbf{y}^{\tau} = i\mathbf{x}\mathbf{y}^{\tau} = -\mathbf{x}(-i\mathbf{y})^{\tau} = -\mathbf{x}(A^{\tau}\mathbf{y})^{\tau} = -\mathbf{x}\mathbf{y}^{\tau}A = -BA.$$
Taking conjugates and using that $A$ is in $M_n(\mathbb{R})$, we get that the conjugate $\bar{B}$ of $B$ anticommutes with $A$. This proves that any linear combination with complex coefficients of the matrices $B$ and $\bar{B}$ anticommutes with $A$. Consequently, $B$ or $i(B - \bar{B})$ is a nonzero matrix in $M_n(\mathbb{R})$ that anticommutes with $A$. This proves the first part of the problem.

We shall prove the converse. Let $B$ be a nonzero matrix in $M_4(\mathbb{R})$ that anticommutes with $A$. Then
$$A^k B = (-1)^k B A^k, \quad k \in \mathbb{N}. \qquad (*)$$
Consider the characteristic polynomial $f$ of $A$,
$$f = \lambda^4 - (\operatorname{tr} A)\lambda^3 + a\lambda^2 - (\operatorname{tr} A^*)\lambda + \det A = \lambda^4 - (\operatorname{tr} A)\lambda^3 + a\lambda^2 - (\operatorname{tr} A)\lambda + \det A,$$ where $a$ is a real number (the latter form of $f$ is a consequence of $\operatorname{tr} A = \operatorname{tr} A^*$).
By Hamilton-Cayley, $f(A) = O_4$. Taking into account $(*)$, we successively obtain:
$$\begin{aligned} O_4 &= f(A)B = B(A^4 + (\operatorname{tr} A)A^3 + aA^2 + (\operatorname{tr} A)A + (\det A)I_4) \\ &= B(f(A) + 2(\operatorname{tr} A)(A^2 + I_4)A) = 2(\operatorname{tr} A)B(A^2 + I_4)A. \end{aligned}$$
Because $\operatorname{tr} A \neq 0$ and $A$ is invertible, we obtain that $B(A^2 + I_4) = O_4$. As $B$ is nonzero we conclude that $A^2 + I_4$ is singular.