I assume spectral decomposition of a symmetric matrix does cost too much. Let $PXX^TP=\Lambda_1$, $QYY^TQ=\Lambda_2$ be spectral decomposition of $XX^T, YY^T$, respectively. Here $\Lambda_1, \Lambda_1$ are diagonal and $P, Q$ are orthogonal. Then $$K^{-1}=(P\otimes Q)^T(I+\Lambda_1\otimes \Lambda_2)^{-1}(P\otimes Q).$$

$(I+\Lambda_1\otimes \Lambda_2)^{-1}$ can be read directly.

I assume spectral decomposition of a symmetric matrix does not cost too much. Let $PXX^TP=\Lambda_1$, $QYY^TQ=\Lambda_2$ be the spectral decomposition of $XX^T, YY^T$, respectively. Here $\Lambda_1, \Lambda_2$ are diagonal and $P, Q$ are orthogonal. Then $$K^{-1}=(P\otimes Q)^T(I+\Lambda_1\otimes \Lambda_2)^{-1}(P\otimes Q).$$

$(I+\Lambda_1\otimes \Lambda_2)^{-1}$ can be read directly.