Hey there Quartz!
A modest suggestion: for Legendary Strength, just say that Kratos automatically succeeds on any Strength check, no matter what is tried.
I have been wondering about the wording revolving around the Legendary [Ability Score] powers.
Legendary Strength is not the top end of where this all goes, there is also Transcendental Strength and Omnipotence (aka Omnific Strength).
My thoughts on Legendary Strength are that it would allow you to lift anything 'ON' the planet, but it wouldn't allow you to juggle moons or whatever. So although Legendary Strength allows you to seemingly do the impossible, it does have an eventual limit - albeit one you are likely not going to reach until you get to the crazy beyond immortal tiers of play.
You might limit automatic success to non-divine opponents and obstacles and give him advantage against divine ones.
Absolutely. Certainly he wins against anyone without Legendary Strength (or better) themselves.
This avoids the problem of saying it's +100 Str when he meets someone with +110 Str.
Hypothetically Kratos could meet someone with Transcendental Strength, in which instance his own strength would be ant-like in comparison, but you don't encounter those beings until you hit the 6th dimension (that place would be a bit too dangerous for Kratos).
This plays off the maxim that you only get to roll if the result is in doubt. Against non-divine opponents and obstacles the result isn't in doubt so no roll is necessary.
The whole reason I chose +100 in the first place was to try and maintain the balance.
Initially my plan was that a blow using Legendary Strength would flat out drop a target to 0 hit points if they failed a save (DC 30), save for damage equal to their bloodied value. Gods & (Legendary) Monsters could use Legendary Resistance to avoid this. In this instance you could not use Legendary Strength more than once per turn.
It may be my initial plan was stronger (no pun intended).
As an aside, the earliest you can get any Legendary Ability Score is CR 28 (Lesser God or above) and such beings would be notably beyond epic tier parties in terms of threats and yes I know official monsters of CR 28, 29, 30 exist and they get REKT by epic parties all the time, but those ain't my CR 28 monsters. As far as I can discern, all official monsters of around CR 15 or more would be better off having their CR's dropped by about 20%, or their stat blocks reworked to make them CR compliant to the Dungeon Masters Guide's rules for HP/DPR by CR.