Weird edge on flat plane
I found a way to make it flat.

There is a second fill option (not fill holes) with ALT + F or under Mesh -> Faces -> Fill (with tries)

With this it worked.

EDIT:
There is a third fill option (GridFill) with Ctrl + F (with quads)

Thanks to Mr Zak in the comments.