There are altogether three Capture Challenges in the game which test your skills in capturing, and also the only places where you can find some of the Pokémon. For the Plains and Sea challenges, there are certain tricks in finding certain Pokémon which do not normally appear.
Plains Capture Challenge
The Plains Capture Challenge takes place at the Kisara Plains in Ring Town, and is hosted by MC Harapper. It is like the Safari Zone in the original handheld games and lets you ride on a Doduo can capture as many Pokémon as you can within 3 minutes inhabiting the plains.
In order to make Slowpoke appear, you must first capture the two Abras. Slowpoke will then appear in the plains on the southern side near the middle.
You normally should have captured a Rapidash during missions, but you can make it appear in the Kisara Plains again by capturing two Spoinks.
Gardevoir can be found at the Cycla Mountain Range, but you can also make it appear here by capturing two Kirlias.
Fearow only appears in the Kisara Plains if you have beaten the high score of Hayate at the Capture Arena in Fall City. Fearow will be to the very north of the plains. It may not fly down to meet you, so run into the Spoink next to it when it is just next to you, it will be drawn into the battle screen as well.
Doduo is quite tricky to find, and requires quick capturing skills, because you must capture two Gardevoirs, and to do that, you must first capture two Kirlias. Doduo will appear in the southern side again just outside the trees.
Dodrio only appears in the Kisara Plains if you have beaten Joe's high score in the Plains Capture Challenge. It will appear in the bush towards the very left, just walk straight down from the entrance.
Skarmory only appears in the Kisara Plains if you have beaten Kamuri's high score in the Sea Capture Challenge in Summerland. It will appear towards the very right, and will swoop down to you upon seeing you.
Sea Capture Challenge
The Sea Capture Challenging takes place at the Saffra Sea in Summerland, and is hosted by MC Fisher, using a similar concept as the Plains Capture Challenge but lets you ride on a Lapras instead and capture water Pokémon. You cannot play this on your first visit to Summerland, but only do so when you have befriend the Lapras Man in Fall City in a later mission. Most water Pokémon appear as darkened patches on the water only, so you really won't know what they are until you run into them.
You should have captured a Kingdra during missions, but to make it appear in the Saffra Sea, capture two Horseas. Horseas and Kingdras are all found near the left patch of darkened waters, but they usually swim just outside of the patch on the south.
Seaking will appear after capturing two Goldeens. They both near the left patch of darkened waters, just around the oddly shaped rocks to the south.
Starmie will appear anyway on the ocean surface after you have captured two Staryus. They will probably come after you, and you don't have to look too hard.
Mantine lives right in the left patch of darkened waters where Remoraids and Octilleries are. Capture two Octilleries and two Remoraids to make Mantine appear.
Sharpedo will appear in the foggy waters on the bottom right after you have captured two Carvanhas. They swim on the surface, so they shouldn't be hard to identify.
Wailmers will appear where Goldeen and Seaking are, only after you have captured two Seakings. This might get tough because Seakings won't appear until you have captured two Goldeens.
Luvdiscs live in the right patch of darkened waters, but the waters are usually murky until you have captured a few Remoraids on the left patch of darkened waters. Luvdiscs often appear in groups, so you might have to capture several of them together.
Towards to bottom left, there is a shadow casted on the waters by a sunken ship. Psyduck will appear there after you have captured two Starmies, which won't appear until you have captured two Staryus, so in other words, quite a long chain reaction here.
Pelipper appears near the light tower in the middle of the sea, but it will only hover around and you must run into another Pokémon near it, and hopefully draw it into the same battle screen. Pelipper will only appear after you have beaten Kamuri's highscore in this same challenge.
Capture Arena Challenge
The Capture Arena is found towards the west of Fall City's market, and will not be accessible until after the credits roll. It is hosted by MC Arena, and is arguably the most difficult of all in all three challenges. You do not actually find any exclusive Pokémon here, but beating Hayate's highscore here is the only way to unlock Fearow in the Plains Capture Challenge. You are only given 2 minutes in this challenge, and Pokémon will fall onto the screen one after another, which you must capture to gain score.
After about 10 Pokémon, you will challenge the leader Pokémon of that rank, and once you succeed capturing the leader, you will proceed to the higher ranks with Pokémon that reward higher scores.
If you wait a bit, a second Pokémon will drop onto the screen. Capturing two Pokémon together will double your score for each Pokémon. While it is true that the number of Pokémon you capture will directly multiply your score by that same amount, the first two ranks only show a maximum of two Pokémon at any time. But in the third rank, three or more Pokémon may appear at the same time, and it is essential to make use of this multiply factor.
Everytime you succeed in capturing a Pokémon, you time will be extended slightly, depending on how many Pokémon you capture altogether. Technically, no matter how quick you capture Pokémon, you will not be able to beat Hayate's highscore if you simply capture the Pokémon one after another.
The word of advice is, capture Pokémon as soon as they appear for the first two ranks, but once you are in the third rank, wait til 3 Pokémon are on together before you catch them altogether. It seems to be the only way to reach Hayate's score.