Plan out everything that you can. If you don’t have enough to get the star you want, don’t bother committing - remember, there are new troops every week, and the more there are in a kingdom, the less resources you have to commit to get those stars. Going for stuff “early” will just end up costing you more resources in the long run. Additionally, the more low rarity (UR or below, preferably), the easier that kingdom will be to get stars on, especially if you have to start throwing down traits to get stars.
The kingdom list found here is very useful for finding out your best tribute options:
Starting at gold stars, you’ll probably want to consider glory first, then souls, then gold. Gold stars shouldn’t be cost prohibitive yet, but if you are missing some troops in a kingdom still, you might want to focus on another one first. Start with high glory, 9+ troop kingdoms, and just move down the list. Level troops that you aren’t going to use as little as possible (by cost, starting with commons) to minimize the resource commitment as higher levels cost much more souls. Try not to commit any runics or arcanes at all, if possible, for just kingdom stars unless you have exhausted other options.
If you can collect frequently, you probably want as many 3*'s as possible to maximize your gem and gold key income. Start with one high glory kingdom (Whitehelm, Pans Vale, Wild Plains) as your home kingdom, then try to get that to 3* as cheaply as possible. From there, you’ll either want to move onto the kingdoms where you have the most troops unlocked (Khetar, Ghulvania, and Mist of Scales all have 10 available) to maximize keys and gems over time, or higher glory for slightly more cost (the previously mentioned glory kingdoms, then the 9 troop kingdoms with decent glory including Swords Edge, Pridelands, Drifting Sands, and Zhul’Kari).
If you collect less frequently, you’ll probably want to just maximize your glory chance for your investment. Start your 3*'s at Whitehelm, Zhul’Kari, Pan’s Vale (provided you have 9 troops in each) then anything else mentioned you have at least 9 troops in, then anything else mentioned you have 8 troops in, then any other kingdom you have 9 troops in, and finally anything else you have at least 8 troops in. If you have 7 troops in a kingdom, you should skip it until it is your last one or you unlock more troops (or more are released), unless, of course, you are already using and have fully leveled and traited multiple troops in the kingdom.
It may be worth kicking Zhul’Kari and Karakoth (and possibly Pridelands) all the way to 5* while still working on your other 3*'s if you have the extra resources. If you have a ton of souls and just some minor/major traitstones, the 10 troop kingdoms are basically gimmies to get to 5*, so you can pick up those stat points on the cheap (a couple armor and a life) if you want as well, but in my experience, more 3*'s will help more in the long run. I will note that neither of the 5* magic kingdoms that I got had any measurable effect on my PvP or challenge farming speed (except for Tacet’s one-shot “Minon Raid” method, which I decided was not for me anyway) , and that my “fun” teams were the ones that generally got more of a bump.
Keep in mind that even using traitstones to fill the gap, just leveling to get a single kingdom to 3* is likely going to cost between 20k and 30k souls, with levels 15-20 being especially pricey. Once I started working on 3* kingdoms, though, I found tributes to be a MUCH higher percentage of my weekly glory than it was for souls or gold.
Break out that Valk, you are going to need her.