Algo como isso deve funcionar:
:%s/^\(.*[^\n]\)$/* /
EDIT Desde que você solicitou um detalhamento da expressão regular:
:% Todas as linhas
s/ Início do comando substituto; comece o padrão
^ Início da linha
\( Início do grupo que queremos preservar. Isso será importante mais tarde.
.* Qualquer número de caracteres
[^\n] Algum personagem além da nova linha
\) Fim do grupo
$ Fim da linha
/ Fim do padrão, início da substituição
* Insira * , depois o primeiro grupo que selecionamos à esquerda.
/ Fim da substituição e comando