Let’s assume that the manifold $M$ is irreducible and orientable and the surface $S$ is orientable. This is to avoid 1-sided surfaces.
First let’s assume that the surface $S$ is fully compressible. 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 the balls 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 such as lens spaces and the Poincaré dodecahedral space.
In the general case, one compresses down the surface $S$ to a surface $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 if $S’$ is not a collection of spheres (so a component is an incompressible surface of genus $>0$).
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 in the compressible case by reducing to $S’$.
I suspect that there is an algorithm in general like Sam Nead suggests, but I expect that it isn’t written down in general.