Volcanically active islandsareas
The remains of their parents are virtually identical to spent/burnt carbon, char and ash, so why not place them in a region where there's bound to be a lot of it? Volcano goes off, ash falls, worms feast on the layers building up and become fat and happy before their eventual metamorphosis into the pheonix.
Should an islandarea cease to be active for some reason the birds could fly to another one that is active and continue their existence there, or even go to a mainland volcano if it's active enough. The birds would be able to tell its activity by the rumblings and the heat of the area and would then determine whether or not it's a good place for them to die should they eventually do.
The only problem the worms would then have are predators and lava flows, but I'll assume they have that covered, somehow.