Это будет работать для вас:
sed 'N;/<Location \/>\n *Order allow, deny/s//&\n Allow from all/;P;D' file
или альтернативно
sed $'N;/<Location \\/>\\n *Order allow, deny/a\\\nAllow from all\nP;D;' file
Пример
$ sed 'N;/<Location \/>\n *Order allow, deny/s//&\n Allow from all/;P;D' cups.in
# other stuff here
# Restrict access to the server...
<Location />
Order allow, deny
Allow from all
</Location>
stuff
$ sed $'N;/<Location \\/>\\n *Order allow, deny/a\\\n Allow from all\nP;D;' cups.in
# other stuff here
# Restrict access to the server...
<Location />
Allow from all
Order allow, deny
</Location>
stuff
Обратите внимание, что порядок добавления Allow from all
отличается, хотя я не верю, что это немного отличает функциональность.