How about something like:
includes = $(wildcard include/*.h)
%.o: %.c ${includes}
gcc -Wall -Iinclude ...
You could also use the wildcards directly, but I tend to find I need them in more than one place.
Note that this only works well on small projects, since it assumes that every object file depends on every header file.