$C$ will admit a nontrivial rational map to an elliptic curve $E$ if and only if $E$ appears as an isogeny factor of the Jacobian $J(C)$. So in some sense it is impossible to avoid what you lament in your first paragraph.
However, we don't necessarily need to compute the Jacobian $J(C)$ in any sense: rather, we need to show that it does not have an elliptic curve as an isogeny factor. The conventional wisdom is that (if $C$ has genus greater than one, as you must of course intend) then it is very likely that $J(C)$ is geometrically simple and even that $\operatorname{End} J(C) = \mathbb{Z}$.
There are some sufficient conditions for that! The one I know by heart is the following beautiful theorem of Zarhin:
Let $K$ be a field of characteristic different from $2$, and let $C_{/K}$ be a hyperelliptic curve given by $y^2 = P_{2g+2}(x)$. Then if the Galois group of
$P_{2g+2}(X)$ is $S_{2g+2}$ (as it usually is!!) or $A_{2g+2}$, then $\operatorname{End} J(C) = \mathbb{Z}$.
Unfortunately I have forgotten much of what I used to know about this sort of thing, but I am reasonably confident that there are further results along these lines. The name "Arsen Elkin" (whom I think was a student of Zarhin) is coming to mind.
It would be very interesting to have a criterion that one could apply to a fairly arbitrary plane curve $C$ that would be sufficient to force its Jacobian to have endomorphism ring $\mathbb{Z}$. This time I have no memories, however dim, of such a result, but it would certainly be nice...
Added: I looked up Elkin's work on MathSciNet. He has several papers in this area, but so far as I can see they all further refine the hyperelliptic case.