Instalei Fedora 19 KDE Spin, porém, mesmo selecionando o idioma Português do Brasil durante a instalação, o sistema ficou em Inglês após a instalação.

No Xfce Spin, não aconteceu isso. Tudo ficou em Português.

Pois bem, para instalar o pacote de idiomas do KDE, eu fiz:

sudo yum install kde-l10n-Brazil

Após isso, nas configurações do sistema, pude escolher o idioma.
Basta reiniciar a sessão, depois disso.

Abraço.