but they have a Turkic family language there, not a Slavic one
In Europe, Polish and Irish are two examples of a language with extensive contrastive palatalization which uses the Latin alphabet, and they're probably among the least readable/elegant writing systems in Europe.
Sure, many languages have palatalized consonants, influenced by surrounding phonetic context (such as, vowel harmony in Turkic makes surrounding consonants "softer" too).
The true "contrastive palatalization" I was referring to is about having minimal pairs where words have totally different meanings based on whether the consonants are palatalized or not.
For example, in Russian (where I specify the palatalization of a preceding consonant with ʲ):
mer "a mayor"
mʲer "of measures"
mʲerʲ "measure!" (imperative)
Latin alphabet has no means to express it naturally, while in Cyrillic there're already all the required letters for it. Just omitting it in writing will introduce confusion.