Proof of non-regularity, based on the Kolmogorov complexity
To my knowledge, this is not one of the "classical" approaches used to characterize regular languages.

This approach is discussed in "A New Approach to Formal Language Theory by
Kolmogorov Complexity", by Ming Li and Paul M.B. Vitanyi (see section 3.1).

They give several examples where one can use the statement you mentioned instead of using the pumping lemma. For example, proving non-regularity of $L$ where

$L=\left\{1^p|\text{p is prime}\right\}$.

Given some $x\in\Sigma^*$, $L_x=\left\{y| \hspace{1mm} xy=1^p \land \text{p is prime}\right\}$. Let us choose $x=1^{p'}$ where $p'$ is the $k$'th prime. Let $y_1$ be the first word in $L_x$. Obviously, $y_1=1^{p-p'}$ where $p$ is the $k+1$ prime. According to the statement you mentioned, $K(y_1)\le c$ ($n=1$), for some constant $c$ depending only on $L$ (see paper).

Since this holds for all $x$, we can bound the Kolmogorov complexity of all elements in $S=\left\{y_1^x| x=1^p \text{ for prime $p$ } \land \text{$y_1^x$ is the first string in $L_x$}\right\}$ by the same constant $c$. However, we saw that $S$ actually consists of differences between consecutive primes, i.e. 
$S=\left\{1^{p_{k+1}-p_k} | k\ge 1\right\}$ where $p_k$ is the $k$'th prime. Since we know $S$ cannot have bounded Kolmogorov complexity (prime differences get arbitrarily large), this means $L$ cannot be regular.