$K$ が $4,5$ の倍数の場合は明らかに存在しません。また、 $K=1,2$ の場合は答えは $1$ であり、 $K$ が ( $4$ の倍数でない ) 偶数ならば $K$ を $2$ で割っても答えは変わりません。
$K$ がこれらを満たすとして、問題は $10^n \equiv 1 \left( \mathrm{mod}\ 9K \right)$ を満たす最小の正整数 $n$ を求めるものに帰着できます。これを考えます。

初めに、 $9K=p_1^{d_1} p_2^{d_2} \cdots p_m^{d_m}$ の形で素因数分解します。

ここで、 $10$ と互いに素な素数 $p$ と正整数 $x,d$ について、 $10^x \equiv 1 \left( \mathrm{mod}\ p^d \right)$ ならば $10^{px} \equiv 1 \left( \mathrm{mod}\ p^{d+1} \right)$ が成り立ちます。

証明

$p^d = t$ とする。この時、 $0$ 以上の整数 $s$ で $10^x = st+1$ を満たすものが存在する。ここで、 $10^{px} = (10^x)^p = (st+1)^p = \sum_{i=0}^{p} {}_p C_i \left( st \right)^i$ がいえる。
ここで、 $1 \leq i \leq p-1$ について、 $ {}_p C_i \equiv 0 \left( \mathrm{mod}\ p \right)$ であり、これと $\left( st \right) ^i \equiv 0 \left( \mathrm{mod}\ t \right)$ より ${}_p C_i \left( st \right)^i \equiv 0 \left( \mathrm{mod}\ tp \right)$ となる。また、 $t^p = p^{dp}$ であり、 $p \geq 3$ より $dp \geq d+1$ であるので $t^p \equiv 0 \left( \mathrm{mod}\ tp \right)$ である。これより $\left( st \right) ^i \equiv 0 \left( \mathrm{mod}\ tp \right)$ が成り立つ。
よって $10^{px} \equiv 1 \left( \mathrm{mod}\ tp \right)$ であり、示された。

言い換えると、 $10$ と互いに素な素数 $p$ と正整数 $x,d$ について、 $10^x \equiv 1 \left( \mathrm{mod}\ p \right)$ ならば $10^{p^{d-1}x} \equiv 1 \left( \mathrm{mod}\ p^d \right)$ が成り立ちます。

これとフェルマーの小定理より、 $10^{p_i^{d_i-1} \left( p_i-1 \right)} \equiv 1 \ ( \mathrm{mod}\ p_i^{d_i} )$ が成立します。よって、 $n$ は $G = \mathrm{gcd} ( p_1^{d_1-1}\left( p_1-1 \right) , p_2^{d_2-1}\left( p_2-1 \right) , \cdots , p_m^{d_m-1}\left( p_m-1 \right) )$ の約数であり、 $p_i^{d_i-1} \left( p_i-1 \right) \leq p_i^{d_i}$ より $G \leq 9K$ です。
よって、 $G$ の約数 $div$ すべてについて $10^{div} \equiv 1 \left( \mathrm{mod}\ 9K \right)$ かを確かめればよく、このような $div$ は $G$ の約数の個数 $d(G)$ だけ種類があり、ここの計算量は $O( d(G) \log G)$ です。

素因数分解は $O(K^{\frac{1}{4}})$ で可能なので、この問題は$O(K^{\frac{1}{4}} +d(G) \log G )$ で解くことができました。 $K \leq 10^8$ において $d(G) \leq 1344$ であるのでこれは十分高速です。

実装例(C++)