POSIXly (also valid in sed), Only one regex used, need memory only for one line (as usual):
sed '/\(#include\).*/!b;//{h;s//\1 "newfile.h"/;G};:1;n;b1'
Explained:
sed '
/\(#include\).*/!b # Only one regex used. On lines not matching
# the text `#include` **yet**,
# branch to end, cause the default print. Re-start.
//{ # On first line matching previous regex.
h # hold the line.
s//\1 "newfile.h"/ # append ` "newfile.h"` to the `#include` matched.
G # append a newline.
} # end of replacement.
:1 # Once **one** replacement got done (the first match)
n # Loop continually reading a line each time
b1 # and printing it by default.
' # end of sed script.