Yeah, Herman is the person that tells you about Black's Cave and is also the person you need for the quest. You've already gotten Vanguard to move, so I don't think you can recruit him any longer, but it may be possible by recruiting Nora then visiting the tavern in Pidona and talking to the barkeep. The flag for him telling you about Red Coral around where Herman is has always been wonky and might not work, but it is probably your best shot.

Paul can be recruited in two ways. The first is to lose to the thieves during the missions from the man in the Lance weaponshop with an open party slot and a non-Nora/Ellen female party member. The second way is to visit Nina's house after clearing an Abyss Gate -- she's in the town with the Sacrificial Cave quest in the bottom right house.

You've been in the town with the Ring, and probably talked to the person that has it honestly, but he won't mention it or give it to you until you've seen Arakes' door. You are supposed to piece together where it is from one of the comments you hear in the top-right house in the northern part of Pidona, but even then the hint isn't super clear.