I want to argue that in the case in which X and Y are surfaces that are not ruled, then you can decide if they are isomorphic or not.
Computationally you can decide if the surfaces are rational (P_2=q=0) or ruled (P_{12}=0). I will ignore these cases, even though it might be possible to decide them; in any case, you can easily determine the birational isomorphism class of X and Y.
Compute the Kodaira dimension of the surfaces by computing the image under the linear system |12K|. If the surfaces are of general type, then we are more or less done since any isomorphism must come from a linear isomorphism of the ambient projective space under the "embedding" given by |5K|. If the Kodaira dimension is one, then you essentially reduce to computing the base curve of the elliptic fibration and the corresponding morphism to the j-line: this information seems to be pretty computable!
If the Kodaira dimension is zero, then you look for exceptional curves on your surfaces (using Hilbert schemes) and contract them, until $K^2=0$. The final surfaces will be one of Enriques, bielliptic, Abelian and K3 surfaces; these classes are easily discernible by $p_g$ and q. Note that replacing X and Y by their minimal models in these cases does not affect the computability of an isomorphism. (This reduction may not be needed, but it makes me feel safer; note also that you can probably do this more efficiently by looking for effective divisors in (multiples of) the anticanonical divisor.)
Enriques surfaces seem to be decidable since their ample bundles do not vary, so you can get them all in the same projective space and reduce the isomorphism to an ambient linear isomorphism.
Bielliptic surfaces roughly reduce to the case of curves.
Abelian surfaces correspond to genus two curves and are therefore again recognizable.
Finally we get to the interesting case: K3 surfaces! (Recall though that we left out rational surfaces.)
Determine very ample line bundles $A_X$ on X and $A_Y$ on Y. Just to be on the safe side, decide if the two embeddings for X and Y that you obtain are not the "same"! Assume they are not the same.
Here is where the real meat of the argument is (and where I might have made my most serious mistake). Find models of X and Y over the same finite extension of Q and find a prime p that is of good non-supersingular reduction for both X and Y and reduce them modulo p. Using the known Tate-conjecture in this case we can compute the (geometric) Picard lattices (up to tensoring with Q) of the reductions by looking for new divisors until we find enough whose intersection matrix has the appropriate rank. We can establish an isomorphism of the corresponding rational vector spaces with intersection form, find a vector in this vector space that is represented by an effective divisor in both surfaces and has positive square. The image under such a line bundle of the two surfaces will allow us to find an isomorphism between the two sufaces in positive characteristic. The outcome of all this is that now we can find out what lattice do the two ample line bundles $A_X$ and $A_Y$ we started with on X and Y span in their respective Picard groups: it is the lattice spanned by their images in the Picard group of the reduction!
So now we go back to our surfaces X and Y and their ample line bundles $A_X$ and $A_Y$. We know the degree and the genus of the ample line bundle $A_Y$ of Y under the embedding of X given by $A_Y$, and we look for such a divisor in the Hilbert scheme: there will be finitely many possibilities. We check all of them and we conclude!
I hope that the above is correct, or at least that it is recoverable if it isn't!