If you do not want to differentiate gender of a person being referred to, for instance in public or legal notices, why is there no single word for the following word pairs?
(he,she), (him,her), {his,her)
It appears to be a big limitation in many languages...
To answer your question as to why there is no single word for the pairs, I cannot definitively state. However, I can point out that we are a race that possesses two distinct genders and, for much of human history, has had little need to address audiences with which we were not familiar (thus no need for gender-neutral language).
Adding to this is our system of honorifics. They come in gender-pairs: Duke and Duchess, Baron and Baroness, Mr and Mrs/Miss/Ms, Lord and Lady, etc. Even gender neutral honorifics like "Majesty" still acquire gender-specific nomenclature to assume their various word forms ("What would please His Majesty?" "Does Her Majesty require aid?").
But to bring this back to your second point, the reason that public and legal notices must go with both words is because there is an inherent vagueness that accompanies using words such as they and their to represent people that is unacceptable in some legal contexts.
Take the following examples:
He ate his apple after she ate hers. He shall relinquish his weapon before entering the building. She shall pay for her crime.
vs
They ate their apple (the context of apple points toward singular). They ate their oranges (now the context points to, but does not definitively confirm, plural; one person could be eating many oranges). If someone is caught by the metal detector, they shall be compelled to empty their pockets (again, context is singular). They shall be punished for their crime (without context, both options are just as likely).
