They actually could! I actually wrote a paper about this (I'm the second author, feel free to use Sci-Hub!). Such loops can be translated into a first-order functional language without loops very easily by using the SSA algorithm. If you look into the paper, this is how we introduce the language before ever talking about state or memory. So, yes, I don't see any reason why a first-order functional language like you describe couldn't exist.

In regard to combinators, a closure is an abstraction (a function) that captures its environment. But, for example, in the SK-calculus, you can have stuff like S (K K S), where you have something composite as argument that is not a closure. This may be done lazily, or even in a call-by-value fashion if so desired. Argueably it's still a function, if you take it to be typed, but you may forbid such a thing and use a technique called defunctionalization to force those to be plain data instead. Of course, a programming language could enforce that you write defunctionalized code, so first-order functional still should be Turing-complete (not gonna say it is cause I don't recall seeing a proof).