Let’s assume that the manifold is irreducible and that the surface $S$ is fully compressible and everything is orientable. That means that there is a sequence of compressions taking the surface to a collection of 2-spheres, for example a Heegaard surface. Since the manifold is irreducible, these spheres lie inside of a ball (but they might be nested). Thus we can make $K$ disjoint from them by an isotopy. Reversing the process of compression, we can iteratively tube these spheres together to get back $S$ up to isotopy. In this process, we can assume that each tube misses $K$ by general position (it is a small regular neighborhood of an arc) and hence get an isotopic surface which misses $K$. So this takes care of the case of fully compressible surfaces, which will be the case in a non-Haken irreducible 3-manifold.
In the general case, one compresses down the surface $S$ to a surface $S’$, and one sees that $K$ will miss $S$ if it misses this full compression $S’$. By a similar argument, $K$ will miss $S$ up to isotopy if it misses $S’$ (although the converse is likely not true). In an irreducible 3-manifold, it must be Haken.
Thus assume $S$ is incompressible. In principle then one can determine if $S$ can be made disjoint from $K$. Let me sketch the case that $M$ and $M-K$ are hyperbolic. In this case, one can enumerate the finitely many disjoint incompressible surfaces of the same genus as $S$ in $M$ and $M-K$. There are algorithms using normal surface theory or geometric group theory. Then there is an algorithm to tell if these surfaces are isotopic (in the non hyperbolic case, there may be infinitely many surfaces of a fixed genus, and one has to work harder). If so, then $K$ can be isotoped disjoint from $M$, otherwise not. Of course, this only gives a sufficient condition.
I suspect that there is an algorithm in general like Sam Nead suggests, but I expect it isn’t written down in general.