What does it mean for a language to have "order"?
My angle on a related distinction: http://chrisamaphone.livejournal.com/751991.html

The "order" of nth-order (including higher-order) logic refers to the level of things that can be quantified over. In first-order logic, the things quantified over are terms of some unrelated domain: "All men are mortal." In second order logic, you can quantify over first-order predicates: "All properties of men also hold of dragons." Higher-order logic is the generalization of this to all higher predicates, which I think is better understood in terms of system F-omega (equivalent to HOL), wherein you can form type operators (constructors of kind type -> type) which can be quantified over as well as types.

The relation to "order" in polynomials is better understood as an analogy pertaining to recursion (nth order polynomials include a term multiplied by itself n times) than anything more rigorous.