I have doubts about the connection between the theorem of completeness for first order logic and the axiom of choice. I did hear that AC (possibly in a weakened form) is necessary to prove Goedel theorem. In particular I was told that it was necessary to prove Lindenbaum lemma.
But I have studied this [1] proof and it's not clear to me where are we using AC. Am I missing something or it's not this lemma the culprit?
[1]: Mendelson E., "Introduction to Mathematical Logic", Prop. 2.14
As remarked by Mauro in the comments, when the language you are concerned with is countable, or generally well-orderable, the axiom of choice is not needed. You can just enumerate (or otherwise well-order) your sentences and recursively extend the theory by taking anything which doesn't contradict your theory thus far, and by the end of the recursion you'd have a complete theory.
Indeed, this is a common theme. Choice is mainly needed to obtain a well-ordering of stuff.
In general, however, not every consistent theory can be extended to a complete theory. Perhaps because it has no model. For example, suppose that there exists a set $A$ which cannot be linearly ordered (e.g. an amorphous set). Consider the language in which we have a binary relation $<$ and a constant $c_a$ for all $a\in A$.
Now consider the following theory $T$:
This theory is consistent, of course, since contradiction would follow from a finite fragment of $T$, but any finite fragment has a [finite] model. But a complete theory extending $T$ would have to decide all the statements of the form $c_a<c_b$, which would in turn give you a linear ordering of $A$. Since no such linear ordering exists, there is no complete theory extending $T$.