Can you try with these characters?

À|A, Á|A, Â|A, Ã|A, Ä|A, Å|A, à|a, á|a, â|a, ã|a, ä|a, å|a, Ā|A, ā|a, Ă|A, ă|a, Ą|A, ą|a, Ç|C, ç|c, Ć|C, ć|c, Ĉ|C, ĉ|c, Ċ|C, ċ|c, Č|C, č|c, Ð|D, ð|d, Ď|D, ď|d, Đ|D, đ|d, È|E, É|E, Ê|E, Ë|E, è|e, é|e, ê|e, ë|e, Ē|E, ē|e, Ĕ|E, ĕ|e, Ė|E, ė|e, Ę|E, ę|e, Ě|E, ě|e, Ĝ|G, ĝ|g, Ğ|G, ğ|g, Ġ|G, ġ|g, Ģ|G, ģ|g, Ĥ|H, ĥ|h, Ħ|H, ħ|h, Ì|I, Í|I, Î|I, Ï|I, ì|i, í|i, î|i, ï|i, Ĩ|I, ĩ|i, Ī|I, ī|i, Ĭ|I, ĭ|i, Į|I, į|i, İ|I, ı|i, Ĵ|J, ĵ|j, Ķ|K, ķ|k, ĸ|k, Ĺ|L, ĺ|l, Ļ|L, ļ|l, Ľ|L, ľ|l, Ŀ|L, ŀ|l, Ł|L, ł|l, Ñ|N, ñ|n, Ń|N, ń|n, Ņ|N, ņ|n, Ň|N, ň|n, ʼn|n, Ŋ|N, ŋ|n, Ò|O, Ó|O, Ô|O, Õ|O, Ö|O, Ø|O, ò|o, ó|o, ô|o, õ|o, ö|o, ø|o, Ō|O, ō|o, Ŏ|O, ŏ|o, Ő|O, ő|o, Ŕ|R, ŕ|r, Ŗ|R, ŗ|r, Ř|R, ř|r, Ś|S, ś|s, Ŝ|S, ŝ|s, Ş|S, ş|s, Š|S, š|s, ſ|s, Ţ|T, ţ|t, Ť|T, ť|t, Ŧ|T, ŧ|t, Ù|U, Ú|U, Û|U, Ü|U, ù|u, ú|u, û|u, ü|u, Ũ|U, ũ|u, Ū|U, ū|u, Ŭ|U, ŭ|u, Ů|U, ů|u, Ű|U, ű|u, Ų|U, ų|u, Ŵ|W, ŵ|w, Ý|Y, ý|y, ÿ|y, Ŷ|Y, ŷ|y, Ÿ|Y, Ź|Z, ź|z, Ż|Z, ż|z, Ž|Z, ž|z, α|a, β|b, γ|g, δ|d, ε|e, ζ|z, η|h, θ|th, ι|i, κ|k, λ|l, μ|m, ν|n, ξ|x, ο|o, π|p, ρ|r, σ|s, τ|t, υ|y, φ|f, χ|ch, ψ|ps, ω|w, Α|A, Β|B, Γ|G, Δ|D, Ε|E, Ζ|Z, Η|H, Θ|Th, Ι|I, Κ|K, Λ|L, Μ|M, Ξ|X, Ο|O, Π|P, Ρ|R, Σ|S, Τ|T, Υ|Y, Φ|F, Χ|Ch, Ψ|Ps, Ω|W, ά|a, έ|e, ή|h, ί|i, ό|o, ύ|y, ώ|w, Ά|A, Έ|E, Ή|H, Ί|I, Ό|O, Ύ|Y, Ώ|W, ϊ|i, ΐ|i, ϋ|y, ς|s, А|A, Ӑ|A, Ӓ|A, Ә|E, Ӛ|E, Ӕ|E, Б|B, В|V, Г|G, Ґ|G, Ѓ|G, Ғ|G, Ӷ|G, y|Y, Д|D, Е|E, Ѐ|E, Ё|YO, Ӗ|E, Ҽ|E, Ҿ|E, Є|YE, Ж|ZH, Ӂ|DZH, Җ|ZH, Ӝ|DZH, З|Z, Ҙ|Z, Ӟ|DZ, Ӡ|DZ, Ѕ|DZ, И|I, Ѝ|I, Ӥ|I, Ӣ|I, І|I, Ї|JI, Ӏ|I, Й|Y, Ҋ|Y, Ј|J, К|K, Қ|Q, Ҟ|Q, Ҡ|K, Ӄ|Q, Ҝ|K, Л|L, Ӆ|L, Љ|L, М|M, Ӎ|M, Н|N, Ӊ|N, Ң|N, Ӈ|N, Ҥ|N, Њ|N, О|O, Ӧ|O, Ө|O, Ӫ|O, Ҩ|O, П|P, Ҧ|PF, Р|P, Ҏ|P, С|S, Ҫ|S, Т|T, Ҭ|TH, Ћ|T, Ќ|K, У|U, Ў|U, Ӳ|U, Ӱ|U, Ӯ|U, Ү|U, Ұ|U, Ф|F, Х|H, Ҳ|H, Һ|H, Ц|TS, Ҵ|TS, Ч|CH, Ӵ|CH, Ҷ|CH, Ӌ|CH, Ҹ|CH, Џ|DZ, Ш|SH, Щ|SHT, Ъ|A, Ы|Y, Ӹ|Y, Ь|Y, Ҍ|Y, Э|E, Ӭ|E, Ю|YU, Я|YA, а|a, ӑ|a, ӓ|a, ә|e, ӛ|e, ӕ|e, б|b, в|v, г|g, ґ|g, ѓ|g, ғ|g, ӷ|g, y|y, д|d, е|e, ѐ|e, ё|yo, ӗ|e, ҽ|e, ҿ|e, є|ye, ж|zh, ӂ|dzh, җ|zh, ӝ|dzh, з|z, ҙ|z, ӟ|dz, ӡ|dz, ѕ|dz, и|i, ѝ|i, ӥ|i, ӣ|i, і|i, ї|ji, Ӏ|i, й|y, ҋ|y, ј|j, к|k, қ|q, ҟ|q, ҡ|k, ӄ|q, ҝ|k, л|l, ӆ|l, љ|l, м|m, ӎ|m, н|n, ӊ|n, ң|n, ӈ|n, ҥ|n, њ|n, о|o, ӧ|o, ө|o, ӫ|o, ҩ|o, п|p, ҧ|pf, р|p, ҏ|p, с|s, ҫ|s, т|t, ҭ|th, ћ|t, ќ|k, у|u, ў|u, ӳ|u, ӱ|u, ӯ|u, ү|u, ұ|u, ф|f, х|h, ҳ|h, һ|h, ц|ts, ҵ|ts, ч|ch, ӵ|ch, ҷ|ch, ӌ|ch, ҹ|ch, џ|dz, ш|sh, щ|sht, ъ|a, ы|y, ӹ|y, ь|y, ҍ|y, э|e, ӭ|e, ю|yu, я|ya

Furthermore please doublecheck your unicode Aliases' settings?
docs.joomla.org/International_Enhancements_for_Version_1.6#Unicode_URLs

Is there any extension at your Joomla installation that modifies the url structure ?

No I haven't used this kind of extensions at any point.

Can we try a couple of things?
a) Paste the entire character set for replacements.
b) Try adding a new tag.

It's still wrong. What I did:

I added all the characters you gave (I've tried it earlier, as well), checked the global configuration.

What's symptomatic and what I've noticed is a fact that, when I for example create a new K2 menu item, which is K2 » Item listings » Tag it generates a proper url (lowers the letters adds dash etc). All other Url-s in the template are fine.

The thing is only with the item list by tag, generated from item.

Since, I've added all the characters, you've suggested. The only change is that, when I add a new tag with special characters in it to the item, it doesn't allow me to do so. So a displayed tag) in item is without the special characters (which certainly is not, what we want), so obviously it generates URL without special characters, but also without dashes, and even lowering the letters.

In my browser it looks like this:

www.sportowyobiektyw.pl/wideo/tag/Lukasz Fabianski

For Google it is:

www.sportowyobiektyw.pl/wideo/tag/Lukasz%20Fabianski

There must be an issue within K2, of how it generates URLs for item listing by tag, for tags with special characters - generated from items.

I have tried it on an empty but the same template, for different domain, and it's the same. Please help.

The %20 can be explained here: github.com/getk2/k2/issues/71
From what I can see the special character issue is gone now with the new character replacements.

They don't give, any kind of explanation, they just mention the issue, nothing more github.com/getk2/k2/issues/71

Character replacements doesn't work properly, they only way it works, is that it doesn't display tag words in items with special characters ion my language, which in Polish sometimes even changes the meaning.

It all seems, as a hopeless issue :(

Unfortunately you will have to wait for v3, where you can manually set a tag's alias or you can map these tags into a menu item.