What are the exact meaning of "lower-order structure" and "higher-order structure" in this paper?
Low order/low level information refers to the most granular level of information. This is the most informative in terms of volume of information, but it can often be difficult to conceptualise for humans.

High order/high level information refers to abstractions of the low level information to more intuitive but less easy to describe technically concepts.

An example would be images of faces. The low level information might be the raw $x, y, z$ values of the pixels: their position and colour value. Some high level information might be the direction the face in the images is facing, from what direction the lighting in the image is coming etc.

In the paper cited, the example they use is low level information (node and edge values); high level information (motifs).