I do like the idea of crowning the king early. But this would give one player the advantage much earlier. I think your idea to play to 4 influence would be best.
And I definately agree with team-like battles. I think that could work very well. But do you think two nobles should be able to use both of their special abilities if they were to fight only one noble?
Maybe could award the King, but only give the extra influence bonus after 8 is reached