The key point you might be missing here is that simplistic "nature versus nurture" debates in general are dead. Modern psychology understands that it's always an interaction. Software doesn't run without hardware or vice versa. One evolves much more slowly then the other, but neither is ever fully independent nor determinant.
The only truly tricky part is that there's a lot of details we don't yet understand, especially about sexual orientation.
When it comes to the basic mechanics that underly gender we know a long list of biological facts that influence it at different levels. We know that most (nowhere near all) human individuals have either XX or XY sex chromosomes, and that individuals tend to exhibit various biophysical differences in predictable ways based on these genes. XY tends to mean more testosterone which tends to mean more body hair and muscle mass. All of this has complex influence on patterns of cognition, emotions, etc.
Human cultures in general all have some set of social concepts influenced by these facts. With no significant exceptions that we know of, some destinction roughly resembling "male" and "female" is universally understood, but only roughly. As we've seen, the underlying biology is complex in ways that are superficially obvious (there are individuals who "break the mold" in every culture) but also not easily understood in any complete way. Therefore it's not surprising that important details about what the two broad categories actually mean and how binary or fluid they are, vary widely.
With sexual orientation there are various studies that seem to show there must be biophysical and epigenetic differences at play. But as Nikos' answer shows, there is nothing like "a gay gene", and I'm not sure that any specific casual mechanism has been robustly proven to exist.
The key conclusion I take from all this is that your assertions are overly simplistic and the apparent contradictions dissolve when we recognize that cultural and biological patterns are interdependent.
For example:
Queer individuals, just as cishet individuals, are simply born the way they are: they do not "choose" to become queer
Not wrong, but very incomplete. Queerness is one culturally specific way of recognizing that not everyone is unambigiously heterosexual and male or female. There are biophysical traits that underly at least some (if not all) of this diversity, but we don't know what most of them are or exactly how they work. Meanwhile a person makes choices throughout their life that influences their own behavior, gender presentation, etc. These choices heavily shape (but don't freely determine) whether or not they are perceived as queer in society. And ultimately to identify as queer is an individual choice that isn't determined by biology or even behavior. All of this can be true at the same time.
How is it that we are born bound to be attracted to some genders and not others, and to identify with some genders and not others, not knowing which society/community we are (going to be) born into?"
We're born with DNA which is ultimately nothing but a list of protein recipes. Without those proteins we wouldn't exist. Those proteins profoundly but indirectly influence who we develop into as individuals. The concept of gender is a human interpretation of the complex consequences of statistical and comparative patterns in certain parts of our DNA (among other things). Nobody can read your DNA and predict that you are queer, at least not yet. But even if we ever get to that point it will be a culturally conditioned interpretation of behavior patterns and the biochemistry that influences (but never fully determines) those behaviors.
"If an individual were to be born in a society with different genders (and roles, etc.), their gender identity and sexuality could presumably be different from the current ones, so it cannot be said to be innate"
You would develop differently for sure. You're not literally born with a gender identity or sexual orientation. The same ingredients don't always make the same cake, and even the same cake would be received differently in different cultures. But that doesn't mean the ingredients don't exist.