The reason for all these alternate build tools isn't that Make is hard. The problem is that it's too generic and low-level. It comes with a very limited set of built in rules, after that you're on your own.
For example: If I'm working on a C++ project then I'd like my build tool to be aware of concepts like header files, shared libraries, include paths, compiler options. For me that tool is CMake.
Can I do that in Make? I'm sure I could, but I'd end up with the same problem you're complaining about. I'd essentially be writing my own build system, just implemented in Make. Life is too short for that.
Yes: CMake is a little weird, but it's less bad than all the other options for cross-platform projects, and CMake+Ninja is wonderful. (that said, I do hope something Lua-based like Premake catches on).
I don't think what you describe is possible in make alone. You will have to generate make-files with your header dependencies with GCC -MMd option, you will later have to include these files from your main make file. As you say, its possible but it feels like you are building hacks upon hacks.
Add to that diamond shaped dependencies such as several h files including another generated h file and you're in for many sleepless nights.
For example: If I'm working on a C++ project then I'd like my build tool to be aware of concepts like header files, shared libraries, include paths, compiler options. For me that tool is CMake.
Can I do that in Make? I'm sure I could, but I'd end up with the same problem you're complaining about. I'd essentially be writing my own build system, just implemented in Make. Life is too short for that.