I guess you’d have to say something like ‘min/hans/hendes kæreste er en kvinde/mand/pige/dreng’. Or ‘min/hans/hendes kæreste ... hun/han ...’ if you happen to casually mention them and don’t really want to dwell on the topic of gender.
Yes, but so does ‘girlfriend’ when the person who has the girlfriend is female. At least, that's what it used to mean, and still does to some people, at least as one possible meaning. So it should be accepted as a translation.