"Girl cat and boy cat," yes. "Queen and tom," no, although it seems valid and I imagine it might be used in the world of cat breeding. I opted for list form to encourage further discussion (there may be other terms used that I'm not aware of).
In Russian there are the terms "самка" and "самец" for more technical uses, do these exist in Ukrainian as well?
this doesn't seem common to me, can 'my cat and my cat' be an English alternative? if the meaning is implied in Ukrainian, does the translation need to include it? I would assume it's more common to ask names and gender rather than imply it every time. is this common where Ukrainian is spoken?
Remember these are translation exercises. Your understanding of the language is being tested more than your ability to work out natural sounding English counterparts. (I.e. translation versus interpretation.)
In the wild, I might simply interpret it as "my cats." English doesn't go through as much trouble to point out gender as most other languages, so a more natural interpretation would strip that meaning. However, if there was a reason the speaker specified that one cat was male and one was female, I might very well have to preserve the distinction and say "my female cat and male cat." (The two "my"s would be unnecessarily redundant for English.)