Por padrão, o mecanismo de regex do sed é ganancioso. Isso significa que um padrão sempre corresponde à correspondência mais longa possível. Você deve fazer uma pesquisa não-gananciosa, mas acho que o sed não suporta buscas não gananciosas. Portanto, você deve adicionar um (s) ponto (s) de giro ao seu padrão de pesquisa para que sed encontre a correspondência mais curta possível.
A linha a seguir tenta emular a correspondência não-voraz para o seu caso especial e não exige universalidade, pois um único w entre update e o primeiro where torna o padrão inválido:
sed -e 's/^Update[^w]*where//ig'\
-e "s/^/insert into mytemp select * from mytable where /g" n.txt
Outros mecanismos de regex são compatíveis com esse recurso, como, por exemplo, o de perl e awk .
Mas no seu caso eu acho que uma expressão como essa
sed -e 's/^Update.\+where\(.\+where.*\)$/\
insert into mytemp select * from mytable where /ig' n.txt
seria mais conveniente relacionado ao seu problema específico.
(o \ nas linhas acima só é adicionado para tornar as linhas mais legíveis).