Czech does offer a way of forming the gender-agreeing compounds, but they are much more complex to deal with. If that does not bother you, read on.
That other way only works for compounds with units from 1 to 4 and uses a different agreement between the counted object and the number. Let's start with the present case:
- Čeká na sedmdesát dva/tři/čtyři chlapce.
- Čeká na sedmdesát dvě/tři/čtyři dívky.
- Čeká na sedmdesát dvě/tři/čtyři zvířata.
The agreement and declension work as if the number were just the unit piece, i.e., from 2 to 4. And instead of using the genitive case the way it is for 5-20, the case matches the role of the counted quantity in the sentence. Čeká na ... dívky.
Let's look at the awkward, perhaps even pathological consequence of this, which is that of compounds ending in 1:
- Čeká na sedmdesát jednoho chlapce.
- Čeká na sedmdesát jednu dívku.
- Čeká na sedmdesát jedno zvíře.
Now we have singular nouns. To a native, this just feels awkward. And it gets even worse if we insert a quantifier like "všechno" or a demo pronoun, or even add a past-tense verb that demands the singular gendered agreement:
- Který z tamhletoho dvaceti jednoho muže je jejich bratranec?
- Přišla všechna třicet jedna dívka.
- Čekal na nás všechen dvacet jeden člověk.
My advice would be to simply accept that the natives had a reason for pushing for the fixed compounds whose agreement can be treated much more simply yet satisfyingly. The unsatisfying method I described above was once the only standard method and is still technically correct, even though it often produces comical results.
Sedmdesát is a number greater than 5, so the noun has to be in the genitive case. Since "girls" are countable, the noun also has to be plural. "Dívek" is the genitive plural form of the feminine noun "dívka." You can see the full declension here (click Declension):
So sorry -- clearly I did not read your post carefully enough. But here's the answer to your question, from the Tips and Notes for Numbers 3 (see last sentence):
"Just like we did with 21 through 29, we form the compounds from 31 to 99 by following the appropriate multiple of ten with the appropriate numeral for one to nine, separated by a space. No matter what the gender of the counted entity, we use the feminine jedna and the masculine dva in these compounds."