I know you get to encounter and battle Legendary Pokemon in Companion Mode after the main story, but at what point? I've finished the main story and I check the Companion Mode Job Board (the board on the left) but so far, no challenges yet. Do you have to wait after a certain amount of days?
Like all Pokémon games, Pokemon Mystery Dungeon: Gates to Infinity includes a myriad of Legendary Pokémon. However, unlike the past Mystery Dungeon games, the methods to obtain these specific Pokémon are incredibly varied from the simple encounters in and at the end of Dungeons in the past ones.
After defeating the game, when you get your Pokémon Paradise rank up to Ultra, missions involving Legendary Pokémon start appearing. These missions typically end with the Legendary Pokémon joining your squad
Finally, on the left-hand noticeboard in the Pokémon Paradise, you will get various special missions to various small dungeons. Occasionally, you will get missions to go to strange dungeons. These areas are just simple battles against various Boss Pokémon. These Pokémon are not recruitable and are incredibly strong and difficult to defeat. One, Ho-Oh, can even be battled as a Shiny Pokémon. These missions can also be played through local multiplayer.
So even after you have completed your game, Legendary Pokemon will not just start appearing. You will firstly need to get your Rank up to Ultra and then Legendary Pokemon will gradually start appearing. However you should take note that this can vary and it is not insured when they will appear or not
Source 1 Source 2