Seria mais fácil criar um arquivo com as strings de entrada e de substituição na mesma linha (supondo que nem as strings de entrada nem de substituição contenham espaços). Então você pode fazer algo simples como:
while read n k; do sed -i 's/$n/$k/g' file1; done < fileA
EDITAR:
Depois de ver a resposta de Nykakin, percebi que você pode fazer a mesma coisa com os dois arquivos que você tem combinando a sugestão dele com a minha:
paste fileA fileB | while read n k; do sed -i 's/$n/$k/g' file1; done