All languages have some sort of syntactic structure with their verbs (naturally). All you're doing here is taking a verb and calling it something else. It acts like a verb, therefore it is a verb. The key question is whether there exist nouns (like tangata) that cannot be used the way haere is. If a large class of such nouns exist, haere and words like it are clearly verbs.
In the first examples, I agree that we are seeing a "verbal noun" constructed as if it were part of noun phrase, but, again, that's common as dirt. If that denies the existence of verbs in Maori, it denies the existence of verbs entirely. I don't know of any languages that don't do that in some way. The English/Germanic "to" infinitive construction is a perfect example.
Celtic languages often construct sentences similarly, the only major difference being that the particles corresponding to "ke", "ko", and "ka" are interpreted as forms of an auxiliary verb meaning "to be" ("verbal particles" is probably a better term). Celtic languages also share the preference for VSO syntax, which might suggest that there are deep similarities in the grammars (they use postpositive modifiers as well). In fact, looking at a small online Maori course, many of the examples translate into Gaelic with identical word order.
Your last example however would appear to be an entirely straightforward use of haere as a finite verb with "ka" as an aspect marker, since it lacks any of the trappings of a noun phrase. Maori imperatives as well don't appear to be constructed as noun phrases, e.g.
"Homai te rakau kura."
"Hoatu te ipu ki a Mere."