First of all: No, licenses have nothing whatsoever to do with building anything. You need a Blueprint: Stable (lvl 2) to be able to build a stable level 2.
Mercenary license you can only get from other players for silver. I doubt you could afford one any time soon though, since people sell them for a lot of money (if they sell them at all). However, to get a squad, you only need to build a Military Academy (again as with the stable, all you need to build that is a Blueprint: Military Academy (lvl1). Once you have that building, you can automatically form a squad. If you upgrade the Academy, you can build 2 squads. The Mercenary License from the premium store is only for those who still can't get enough of squads and want even more than the Academy can offer.
However, if you want to go exploring, I would suggest you do this through the Explore button and visit islands with your pets. Squads are only needed if you wish to go to the Battlefield (Battles -> Battlefield), where you combat other player's squads with your own. I would highly suggest you keep your hands off this part of the game for now and first try to master the rest. Getting a viable squad for the battlefield requires a very good team with great genes and tactics, so this means either a lot of breeding for great pets, or very expensive purchases of fitting ones from other players. Usually not really something new players can excel at.