My own point of view is ... To move them "all" or at least most of them to level 4-or-so.
... Doing that isn't as tense on resources and increases your gem income (if you collect the tribute, you get gems equal to all kingdoms that sent tribute minus one - so if 5 kingdoms sent tribute, you get 4 gems; you can collect tribute every hour, starting from time you picked up the goodies).
The gold requirements increase by every level investment, so increasing kingdoms all together by 1 - postpones all your stats by a huge lot. That isn't beneficial by any means.
... So from there - focusing on kingdoms 1 by 1 and leveling them to level 10 straight - is what you want to do.
Magic is considered best, because 1 magic = +1 damage per target per cast.
Attack is considered 2nd best because = you usually take skulls more than 4 times per game, making difference of 4+ points of what happens to the enemy.
Health and Armor = if enemy takes that 1 HP - it cannot be "reused" as magic or attack. Those are flat values that make only so much difference. HOWEVER, if you find yourself dying so quick you can't cast your abilities, nor attack with skulls - a troop surviving with 2 HP being able to cast is much more worthwhile than a troop with 40 attack that doesn't have skulls on the board.
My two cents.
Get level 4 on all kingdoms. Then max out Zhul'Kari, Blighted Lands, Darkstone, Karakoth, Silverglade.
The rest goes with personal preference concerning Tribute Income economy or Stat preference.