Just wanted to point out, since no one else went into detail, that Kyurem's origin seems to be:
1) Arrived on a meteorite in the distant- but not prehistoric- past. 2) Is the remnant left over from the pokémon that split into Reshiram and Zekrom. 3) Both 1 and 2; is the remnant of a pokémon that arrived on a meteor and then divided.
It's stated flat out and Arceus came into being in nothingness and created... everything, but in particular Palkia, Dialga, Giratina, then Uxie, Mesprit, and Azelf.
I suspect, but don't hold me to this, that things like Groudon, Kyogre, and Rayquaza came about during the process of creation. Articuno, Zapdos, Moltres, Ho-oh, and Lugia may have been part of that or more recent. Others are up in the air as far as origins go, such as Latios and Latias, Celebi, Jirachi, Shaymin, and others. Several of these in every gen.
Mew is probably just an ancient pokémon, one of the earliest creations. It's said to have the DNA of every pokémon within it, even referred to as "the ancestor of Pokémon," but that's a matter of interpretation. I mean, several pokémon are directly or indirectly manmade such as Porygon, Castform, and Klink. Elgeeyem are said to have appeared rather spontaneously half a century ago in the desert. They're likely extraterrestrial along with Kyurem, Deoxys, and the heavily suggested Clefairy.
As far as I remember, Entei, Raikou, and Suicune were revived by Ho-oh but might not have been anything special before that.
Not sure where Regigigas came from, but it apparently created Registeel, Regirock, and Regice.
Xerneas, Yveltal, and Zygarde, as far as current information goes, seem to exist in that nebulous "they've been around a long time" area that most of the Legendaries fall into. I mean, there are only a handful that we're ever even given suggestions of origins for. --- "Anything worth fighting for is worth fighting dirty for!"
They are Fairies. They exist in this world, and also in their own world. Xerneas is a Light Fairy, Yveltal is a Dark Fairy, and Zygarde is a dragon - considered evil fairies in the real world mythology of the culture that classified fairies into such orders, and that the game mythology was based off of.