I am really having trouble with this because I think in real life those characters would just part ways - the Paladin can't accept such behavior and the others can't stand the goody-goody Paladin. Of course in the real world parting ways means an end to our game. If it wasn't for his oath I think he would just relent and basically look at alignment as a guideline or belief instead of a code to live by.
So rather than debating alignments (which is so obviously easy to quickly and conclusively resolve) or critiquing the decisions of you, your players, or their characters, it occurs to me that addressing your actual concern may be worthwhile. You're worried they wouldn't realistically stay together with these wild variations in behavior and modi operandi due to differing alignments. Here is what I would suggest:
1. Suspend your disbelief: Maybe it's not realistic, but if hard to explain codependence of random adventurers is what your going to get hung up on in a world of magic and monsters that is a strange line in the sand to draw. It is a conceit of the game that people are always operating in rag-tag teams of adventurers with complimentary skills and stick together. Consider just rolling with it.
2. Question your disbelief: Is it really so unrealistic? People stick together and do things they don't like all the time for the sake of income, survival, friendship, love, social pressure, one or another causes, fear of reprisal, or a simple lack of the will to upend their life by leaving their current situation. The lack of realism here to me seems less "why would people at conflict in this way stay together" and more "why would they do it when they only just met each other".
3. Give them reasons to stay together: Money and a cause brought mercenaries and a paladin together once, perhaps some combination of money and cause can do it again. Or perhaps they have gotten into mutual trouble and need each other to get out. It sounds like some sort of lord of giants would have plenty reason to put a bounty on all of their heads, or maybe just the Paladin, as "the leader" of their home-invading, murder expedition, in which case I suspect even the chaotic neutral characters might feel bad leaving him in the lurch. Maybe you can find something they all actually care about or maybe you can persuade them to care about each other. Maybe they'll find the friendship was the real treasure.
4. Make sure you don't have a metagaming problem: If one character wouldn't attack a fleeing giant who might warn other giants and other characters would, this isn't really something they would have a debate over. The characters wanting to attack would do so unless the other character immediately stopped them. I'm not clear how it ran at your table, but don't give them time to have an alignment debate if there isn't in game time for an alignment debate.