Euclid's first proposition constructs an equilateral triangle given a segment $AB$ via two circles using the segment as radiuses, using $C$ as one of the intersection points of the circles.
I understand that there assumptions made which are not part of the original set of axioms. E.g. that the circles intersect (i.e. such a $C$ exists). Additional axioms would be required e.g. involving some continuity axiom for intersection issue.
But when it turn out that the circles intersect twice, by what criteria is one of the two points chosen? Does this require something similar/equivalent to the axiom of choice or not?
No, the axiom of choice is not needed to provide an element of a single finite set.
What the axiom of choice says is that the product of a set of nonempty sets is itself nonempty.