Some spoilers ahead-
Regirock: Cubi Excellus, the new Garufa Ruins, under Carotos Mountain. To start its quest, use the Darchlight mirror on every crystal of the area.
Azelf: I think Honec Woods.
Type:Null shoud be avaible right afer having Surf, start from Route 3 I think.
The Regis, Shaymin and the Legendary Birds's quest should be avaible once you start the .Karma Files, if I remember correctly.
Some legendaries are only for Paragon, while others you didn't mention are for Renegade.
Example:
Plus, there should be a reward for having legit 999 Black Prisms.
And...as a NG+ mechanic, we have...