You could restart if you really feel like you need to...but you shouldn't have to! Just take some time to grind a bit in older nations and recruit more warriors!
To link with pokemon you have to stand right next to them then select your pokemon and you should see a "Link" option on the bottom, this can only be done when you hit a certain point in the story though!
To recruit warriors just defeat them under one of the following conditions
Defeat under 4 turns OR Defeat with a critical hit OR Defeat without your pokemon losing any HP!
Death by Ailments such as burn or poison dont count!
To recruit Warlords you must defeat them with the above conditions AND the pokemon who deals the finishing blow MUST be a pokemon of a Warlord as well.
You can link with pokemon after you take your 5th nation, and the game talks about it. it gives you an explanation when you enter an area with wild pokes for the first time after that.
As for the game, just use super effectives a lot, the game leads you along along where you can be super effective against most places. If you get stuck on one place you should be able to go back and link with some wilds of the type you need.
Where are good places to grind? Whenever I want to train, the places I check always say something like "There is nothing here"
The later areas, and places that have plenty of warriors and Pokemon hanging out at. If you feel confident enough, try training 3-4 guys as opposed to sending 6, as the less amount of units you send into battle means more EXP divided among them.
"Command and Conquer 4 and Red Alert 3 sucking is the fault of Westwood."-Gaming King's take on why C&C stinks.
If you completely link with a Pokemon, after you finish the fight, select the warrior/warlord that you linked to the Pokemon with using the Info option from the menu, and then press right on the d-pad to select between all linked Pokemon with that character.