Se você tem internet lenta (como a minha) há uma forma bem prática (que eu uso bastante) e poderá ser utilizada por você em várias outras situações no futuro.
Abra o gerenciador de pacotes synaptic. Antes de realizar o procedimento, atualize a lista de pacotes clicando no botão recarregar (isso pode demorar um pouco).
No gerenciador, busque pelos pacotes do KDE4. Marque-os para instalação. Não se preocupe, os pacotes não serão baixados, apenas "marcados" para instalação. A instalação só acontece se você clicar no botão aplicar.
O Synaptic detecta automaticamente todas as dependências que estejam faltando e as marca para instalação também.
Vá ao menu arquivo e selecione o comando "Gerar script de download do(s) pacote(s)".
Um pequeno arquivo é criado e salvo na pasta que você escolheu. Este arquivo é um script que contém uma lista de comandos para baixar os pacotes escolhidos. Esse script usa o wget para baixar cada um dos pacotes.
Pois bem, se você é um usuário que veio do Windows, deve se lembrar do DOS (agora chamado de prompit de comando). Esse script poderá ser utilizado no Windows. É simples, basta mudar a extensão de .sh para .bat. O problema é que para rodar no Windows, você deve baixar a versão do wget para Windows, que pode ser facilmente encontrada na Internet. Pesquise no Google por WGet para Windows.
A vantagem desse método é que, se você for instalar um programa com umas dezenas de dependências (o KDE ou um outro ambiente gráfico, ou mesmo programa como o inkscape), basta selecionar o pacote no synaptic e gerar o script de download dos pacotes. O Synapitc detecta as dependências sozinho e as adiciona no script.
Algumas pessoas não se sentem confortáveis usando o prompit de comando ou o terminal do Linux. Garanto que o método funciona e é muito interessante. Eu recomendo muito que você tente utilizar esta forma, pois acho que é a mais flexível, e vai ajudá-lo a baixar os pacotes atualizados diretamente dos repositórios. Se for experimentar e tiver dúvidas, poste aqui.
Após baixar os pacotes, faça como os colegar escreveram: cole os arquivos .deb no diretório /var/cache/apt/archives e instale-os usando o próprio synapitc. Quando abrir o Synapitc, selecione os pacotes, marcando-os para instalação e clique em aplicar.
Um abraço.