How do I fill an area with faces lined up in a grid over a not flat surface?
Have you tried using only the "grid fill" tool?

Like this, select the hole edge ring:



then  use grid fill:



and you get 



It should work when a grid can be inserted, if it does not, can you post your model (better on https://blend-exchange.giantcowfilms.com/ as it's permanent)?

Edit: following your comment: I opened your file, and tried. 

When I used "grid fill" on that selection, an error is shown, but is not "select two edge loops", it is "connecting edge loops overlap"



Anyway I deleted that "edge" that joins both sides of the "hole", and selecte the whole "hole" edge ring, and then using "grid fill" it shows the error you said: "select two edge loops".

I think (edit2: I was wrong, see below) the problem here is that "grid fill" expect correct topology (eg: only quads), while here you have a nice mesh, but technically the topology is very bad (I know, because I'm very good at bad topology :D). 

In particular (at least) in the beak zone you mesh edge loops are "broken", there are n-gons, tris, and because of this probably the grid fill tool can't decide how your mesh is flowing around that hole, and how it should fill. Ngons are terrible for good mesh tobology. Even tris are, but they are easier to solve, afaik.

An example:



Having and keeping a good topology is fundamental to have good "edge loops" to allow any loop tool to work predictably, and it is also fundamental for mesh animation deformation, btw, for the same reason: a good edge loop flow allows the animation system to know exactly how the mesh should deform. But that's another story.

See this a similar issue answered in the past by @cegaton, 
Curved mesh topology

Sometimes, bad topology can be fixed, but often is a pain, but instead of rebuilding from scratch, another path is to learn retopology, ie, recontruct another "good topology" mesh based on a "bad topology" mesh.

Edit2 : no, I was wrong, the problem is that the hole should have the same number of vertices on left and right, of course (thanks to @Jerryno for correcting me). 

These are the different sides (bottom edge is not subdivided as the top one).



I tried to subdivide it with CTRLR, like



getting



Now, selecting the full edge border again grid tool "completes". It could be necessary to edit span/offset settings, just after applying the grid fill tool, to get better results.

this is bad 



this is better



this seems quite perfect