I've heard that it also means "The likes of Hayate," a slightly insulting phrase along the lines of "I can't believe I lost to the likes of you." And I've seen X no gotoku translated as "something like X" or "the likes of X" in other shows.
So no, "Hayate the Combat Butler" isn't a literal translation at all, just an official title. At least it's not as wildly different as Kimi ga Nozomu Eien -> Rumbling Hearts.
EDIT: Speaking of this series/franchise, does anyone know if SS-Eclipse are still planning on subbing the second season, now that it's being streamed on CrunchyRoll?