O processo de texto sed é estritamente orientado à linha, por isso é muito difícil substituir as novas linhas pelo sed.
Não testado:
cat file |
tr '\n\t' ' ' |
sed -e 's/ CP /\n/g' \
-e 's/Mr[.] Mime/Mr.Mime/g' \
-e 's/ */ /g' \
-e 's/%//g'