Oi Alexandre, acho que bastaria:
sed -E "s/^[A-Z0-9]+/BS/" /tmp/entrada
Já que o sed, por padrão, atua no arquivo inteiro, mas como tem de renomear os arquivos da entrada para o nome gerados na saída do sed (como disse o Itamar, dando colisão, pois serão gerados homônimos), acho que uma matada bonita seria:
$ paste /tmp/entrada <(sed -E "s/^[A-Z0-9]+/BS/" /tmp/entrada) | xargs -L1 mv
Ou seja, o paste junta os arquivos iniciais com os nomes correspondentes gerados e o xargs -L1 joga linha a linha depois do mv.
Para testar e ver funcionar, insira um echo, fazendo:
$ paste /tmp/entrada <(sed -E "s/^[A-Z0-9]+/BS/" /tmp/entrada) | xargs -L1 echo mv