There are many different ways to handle it, especially in Warcraft. Inter-faction team-ups happen fairly often in the later lore, and those are a good basis to having a party made up from different races. They fought together, one saved the life of the other etc. There are a lot of possibilities of making the characters susceptible to mixed party. It might work best if only two characters have a connection like this, because than you can have those problems within the team, which are always nice roleplaying opportunities. So basically choose two people from different factions who have a strong prior connection, and use them to keep the party together in the beginning.
You could play with their enemies being the only familiar thing around, if the game is set in some exotic location. They might dislike each other, but in a foreign place having anything/anybody recognizable could be a breath of fresh air. Getting away from said foreign location (and the locals) could also serve as a basis for the adventure.
Th characters are individuals and their views might differ from the majority's. They could simply not care about the species of the other, because they spent their childhood next to orcs/humans, they were prisoners of war and treated right, are jaded cynics or young idealists. Simple solution, though not very elegant.
I know you said "something else than a common goal", but usually that is the best way to begin something like this. Everything else that keeps a party together, like friendship, reliance on the others or sheer inertia can come with time, but the first steps are the hardest, so you should make sure that they work. Get a third party, maybe a goblin cartel to employ them on a longer quest. Use enemies that attack them both, so survival keeps them together. Sometimes there is no graceful or elegant in-character solutions to problems that come from out-of-character decisions of the players (like playing together with characters from different sides of a war).