better than calling sed for every line of input, which is very slow when there are a lot of files, you can use bash's internal string substitution. It is also good idea to quote the parameters to mv:
Code:
for f in invoice*; do mv "$f" "${f/invoice/paid}"; done