What is the significance of the word "combinational" in combinational logic?
The reasoning behind it seems to be as follows. In a combination the order of elements is irrelevant: in (n choose k) it doesn't matter in which order you pick the k elements. Similarly, a combinational logic circuit is a logic circuit where the order of inputs doesn't matter for the outputs. Note here that "an input" refers to the entire input to the circuit, not the individual lines. So, the intuition is that you give a combinational circuit some sequence of inputs, and "order doesn't matter" is true in the sense that the output for each input is the same, even if you permute the sequence.
This is to be understood in opposition to sequential logic, where the order of inputs does matter, because sequential circuit can have internal state (e.g. flip-flops) that can and usually influence individual outputs.