Ok, I finally figured it out. The issue was with gitlab-runner binary - it was installed with x86-64 arch, so xcodebuild couldn't use My Mac device. Solved the issue by installing a correct arm64 binary, now everything works as expected.
Topic:
Developer Tools & Services
SubTopic:
Xcode