If I remember correctly, the Lupus Labyrinth is NW of Nowarl City. Just go to Nowarl City and walk along the mountains to the west until you find the first gap going north.
You can’t really use Celine. Bummer. I wish they’d used her instead of one Stella or Uriel. However, if you collect all the stuffed animals that increase her trust level, you can get the ending with her. (Collect all the animals and make sure the other characters’ trust levels are less than 200.)
My memory is vague, but I think you get the Jolie Jewel in the Labyrinth by defeating Jolie? Maybe. I’m really not sure on this one. Sorry!