How can a character acquire a contact with a connection higher than 6, if not earned during a Mission?
You can't. Only way to get one is by them being part of a Mission, you doing an excellent job and the contact wanting to do business with you in the future.
Perianwyr isn't as well-connected as you would think though, he's rather limited in many ways. It's easy to assume a dragon has big pull, but if they can only make things happen in fringe cases their connection isn't that special. Someone who can basically only influence several dozen nightclubs? Not that impressive. Heck, I looked at Urubia, with her 100b assets, and I cannot justify giving her more than Connection 5 despite it all, because her only real political pull is within Redmond. Likewise for Kalanyr, fun that he made some smart deals and can backstab people and cause earthquakes, but he rather lacks an actual powerbase.
Just to make that clear: I cannot justify, to myself as GM and even to my mother as neutral advisor, why Urubia should have higher Connection than, or even the same as, the right hand of the Mafia boss of Seattle. Jimmy Mac I consider a 6, Urubia a 5. A dragon with >100b in assets has less influence than someone who cannot even become Capo of Seattle.
Meanwhile, the corp-dudes cannot simply reach out to another corpslave's jurisdiction and cause stuff to happen there, because it'd piss the other off who would complain to the corp for violating the rules.
Leaving that aside, I strongly suspect there won't be a higher-than-6 contact in Missions any time soon. The reason is simple: Missions is meant to be a lower-level campaign where newbies can easily fit in and tag along. A single "No-Availability-Limitation" favor for a run is one thing, having a run provide you with a contact you can use to easily get all the expensive stuff is not only imbalanced because it makes the powerful items too easily available, it also puts too big a gap between the newbies and the lucky vets.
Back to increasing your Loyalty/Connection with contacts outside Missions: I strongly recommend against the idea of karma for that. Simply paying experience without any roleplaying hardly seems like the way to get an NPC to like you more. Do good business with them, do jobs for them, and maybe there will be a storyline where your team does a few jobs and the guy's power base expands if you do it right. The idea that someone blindly likes you far more just because you paid experience points, not even hard cold cash but experience points? Sorry but that doesn't fly with me.
An example: I sent a team on a job to rescue a teen from her kidnappers after dad paid ransom multiple times already and was starting to bleed dry. One of the runners contacted Tosh to help with intel and join in on the job, negotiating a decent wage for him from the other runners. Tosh managed to use his connections to get most of the previously-paid ransom back, allowing himself and the team to get a bigger reward from the Johnson than they would have gotten had they only kept the final ransom sum. Tosh was real happy with that outcome and his Loyalty rose.
Connection is used for a few things. A higher Connection makes a contact harder to reach, he can find more info when asking around, is better at networking, and that's pretty much it. The Social Limit bonus is rather irrelevant after the first few points after all. The erronous dicepool bonus has been errata'd out. So honestly, a high-Connection contact is only useful when a GM makes it useful, through either houserules or noting that your runners are so far from home only this contact is capable of helping them. Which means a Connection 7+ contact isn't as big a deal as you might think, outside Missions rules.
However, how you might get one is simple. As your runners play and grow, they get stronger, better, and earn a reputation. If this reputation is good enough, then yes sooner or later someone will reach out to them. Someone who secretly has a lot of pull and sends them on a really dangerous job, and if they impress them, yes they may score them as a Loyalty 1 contact. But you'll need a big reputation for that, with the ability to take on PR5&PR6 teams fast, the ability to stay out of The Law's hands, the ability to look at a couple of Force 8 Spirits or a dozen Hellhounds and go "alright, let's rock".
Take a look at Brothers United. If your team is capable of getting through an SR5 equivalent of that, including with the Pushing The Envelope doubling of Hybrid Ants at the end, without anyone dying or Burning Edge, then they are at the level for a Connection-9 individual to hire them. Perhaps for that exact job.