Regarding programming paradigms, at least one very important consequence of the completeness theorem is that first-order logic can be used as a formal basis for

Regarding programming paradigms, at least one very important consequence of the completeness theorem is that first-order logic can be used as a formal basis for computation. This is because you can model what a Turing machine does via predicates in first-order logic, describing a relation between states of the machine. The completeness theorem tells us that every semantic consequence of a first-order theory (with a well-orderable language) can be derived syntactically. This means that to derive results of the computation, we only have to systematically search for proofs. Due to the completeness theorem, we know that we won't miss anything (i.e., a result of the computation) that is actually the case. An immediate application is an important programming paradigm called logic programming. See for example Prolog, Mercury, and other languages that are based on this idea.