The key for the cage is on the beach under the bunker, IIRC towards the cliff side. In D2:ED I swam over to that beach doing the start of the fjords before going to Sentinel Island, and missed it heading down the beach killing Black Ring soldiers, but noticed it coming back.
The seeds for the statues can be gotten from 3 large, rather distinctive trees. The first is on a small island near the Grand Knight shrine at the start of the fjords.
