Alexandra and
Katherine share Greek roots and are used internationally.
Victoria/Viktoria and Beatrice/Beatrix also cross borders.
Elisabeth is probably the most versatile for nicknames. For example,
Lys,
Betje,
Else,
Lili,
Liesl. I think
Katherine nn
Katja would go well with it.
Elisabeth also has many other diminutives/forms, including
Lisette and
Isabelle.
Isabelle and
Gabrielle go nicely together. Or
Isabelle and
Colette.