If one has a connect sum of two non-trivial irreducible 3-manifolds $M=M_1\#M_2$, then there is a unique embedded essential 2-sphere $S^2$ up to isotopy (forgetting orientation). Hence the elements of $\pi_2(M)$ realized by an embedded 2-sphere will just be the orbit of this 2-sphere under the action of $\pi_1(M)=\pi_1(M_1)\ast\pi_1(M_2)$. With the identification $\pi_2(M) \cong \pi_2(\tilde{M})\cong H_2(\tilde{M})$ via Hurewicz, where $\tilde{M}$ is the universal cover, we can see that most classes (even primitive) will not be realized by an embedded 2-sphere.

From the proof of the geometrization conjecture, one may conclude that $\tilde{M} \cong \mathbb{S^3}-K$, where $K$ is either 2 points (if $M_1\cong M_2\cong \mathbb{RP}^3$, or $K$ is a tamely embedded Cantor set.
I have some notes describing how this goes. In the first case, $H_2(\tilde{M})\cong \mathbb{Z}$, and the element is represented by an embedded sphere iff it is primitive.

In the second case, one may represent any element of $H_2(\tilde{M})$ by a disjoint union of oriented 2-spheres $\Sigma$. Moreover, we may assume this is minimal, so that if components of $\Sigma$ are adjacent, then the orientations agree (otherwise, we may tube them together to get fewer spheres). If $\Sigma$ is disconnected, the the corresponding class of $\pi_2(\tilde{M})$ cannot be represented by an embedded 2-sphere, and hence the same for $\pi_2(M)$. But $\Sigma$ may be disconnected without being non-primitive, since there may be components of $K$ between each of the components of $\Sigma$ which prevent them from being parallel.
I believe figuring out if such a class is connected should be algorithmic (but not practically), by constructing enough of the universal cover, and then performing 3-manifold algorithms to find the embedded spheres.

However, embeddedness of spheres in $\pi_2(\tilde{M})$ is not equivalent to embeddedness in $\pi_2(M)$. In the case at hand, where there is only one class of embedded 2-sphere (up to the action of $\pi_1(M)$), I believe that there ought to be an algorithm. Pull back the embedded 2-sphere $S$ from $M$ to $\tilde{M}$ to get a surface $\tilde{S}$ with infinitely many components. Then we want to be able to determine whether an embedded 2-sphere $\Sigma$ in $\pi_2(\tilde{M})$ is isotopic to one of the components of $\tilde{S}$. As described in my notes, $\tilde{M}$ is a union of thrice-punctured spheres. We may assume that the components of $\tilde{S}$ are contained in this union of 3-punctured spheres. Then take enough of these 3-punctured spheres to contain $\Sigma$ and be connected, giving a submanifold $N\subset \tilde{M}$. The by Hurewicz, $\pi_2(N)=H_2(N)$. Hence $\Sigma$ will be parallel to a sphere of $\tilde{S}$ iff it is homologically equivalent to a sphere of $\tilde{S}$ in $N$ (up to orientation).

I believe that this approach could be made algorithmic, although not in a practical way.

For the general case, I think there ought to be an abstract criterion that implies embeddedness. By the previous consideration, a 2-sphere in $\pi_2(M)$ lifts to a class of $H_2(\tilde{M})$ represented by an embedded sphere. This sphere separates the ends $E=\partial_{\infty}\tilde{M}$ into two pieces $E_+, E_-$. Then one can associate to this partition an action on a CAT(0) cube complex by Sageev's theory. There is a way to do this canonically in this case using a wall space on $E$, so that the sphere is embedded iff the complex is a tree. I won't delve into the theory, but suffice it to say that the sphere will be embedded iff the partition $\{E_+,E_-\}$ has the property that for each element $g\in \pi_1(M)$ acting on $\tilde{M}$ by covering translations and hence on $E$, either $g(E_+)\subset E_+$ or $g(E_+)\subset E_-$.

Again, it should be possible to make this criterion algorithmic by building "enough" of $\tilde{M}$ to see if a lift of $S$ crosses any of its covering translates in an essential way. One might even be able to make this computable using PL minimal surface theory.