The Mario worlds are full of ways of moving from one world to another. Using one of them would be thematically appropriate.

-Phobos

Your other agent could have rescued your Yoshi from a badfic offscreen before your first mission.

They've been done a lot. ^^

-Leaflets. <a href="https://docs.google.com/document/pub?id=1EBLBndKzvFSIlsExiETAZj9Bgm9-oY5Uc5uNryP88">Agent Constance was given one by her father (who was an author who heard about the PPC); one assumes he wrote in and asked for a brochure, which must have caused quite the kerfluffle.

-OFU graduate. Can Yoshis read and write? Do they know of any fiction at all? If so, your Yoshi could have been a student at an OFU. <a href="http://plotprotectors.tripod.com/JAAKSONS/ch1laurel.html">Nenya and Rosie seem to have gotten the address for the PPC from OFUM.

-Freelance Intelligence work. Send the PPC a badfic of interest, and they might offer you a job. It happened to Architeuthis, and something similar happened to Techno-Dann. Again, this obviously requires knowledge of fanfic.

-Badfic bit part. Can't even count the number of times that's happened.

-Picked up by Intelligence while they're surveying a continuum. This happened to Dassie Hyrax.

-Found a physical door into HQ, like Imbolc, Tango, and Blue. A Yoshi has loads of excuses to be wandering around abandoned castles and the like.

-Glitch. Sort of a plothole, but from the other side: what if a Yoshi is caught in a game glitch? One theory for the PPC's nature is that it occupies the space between canon dimensions, so if a glitch dropped the Yoshi right out of the game, PPC HQ is a good place for it to end up.

-Teleport gone wrong. You can't seriously tell me that no game ever has featured both Yoshis and teleportation.

-Followed an agent home. This is essentially 'badfic bit part' without the requirement for them to be from a badfic. It's not like portals filter out who goes through them!

-Taken home by an agent as a souvenir, in egg form, and then raised in the Nursery. It'd be nice to see a second-generation agent (assuming it saw its abductor as a parent-figure), and to hear from someone raised in the Nursery.

Etcetera, etcetera, etcetera. There's not very many limits on what you can do.

hS

Valon, Kala and Gabby were the most straightforward about it; they were just walking around when suddenly big silvery hole (in Kala's case, right above Makes-Things).

I was a little more elaborate with Chakkik's story, though. Basically, someone playing Secret of Mana failed to correctly perform the Ninth Sword Orb glitch, and one of the side-effects of doing this incorrectly is completely and utterly ruining your copy of the game. Chakkik got shunted through a plothole while (from his perspective) his world was torn apart.

I'll call plagiarism if you say that your guy came from a glitched copy of Yoshi's Island, though. :P

Just a plothole. That's how just about everyone arrives. They're all over the multiverse; even World One isn't safe. Agent Yoshi was probably walking along one day when he fell through one.