The only thing you actually need to trigger the appearance of the leopard woman in the village is to accept Uhara's challenge in spear throwing, and complete it one time. You can lose; winning does not matter. The bridge challenge is also not important. To make her appear to challenge you, you must have a Throwing skill of 125.
For freeing her, she needs to be dispelled. Complete the manhood trial (as long as you help Yesufu when he is stuck you do not have to win), talk to the Laibon about the bride price, exit, reenter and talk about marriage. As long as you have the items for the bride price, you will buy her freedom. Head to the cage. If Uhara or Yesufu are there, leave and immediate reenter. You do not have to give her gifts; as long as it is the nameless guard, you can open the cage and let her out.
When she runs off, head to the jungle and she appears as a random encounter. When you get an encounter with no monster, use the Mouth icon to call put to her.
I posted a speed run on Youtube. Look up mrprmiller and I have routed the first four games, and have posted speed runs of all the classes for them. They are Any%, so they do the minimum neccesary. There is a Paladin run of QFG3 too.
If she is not appearing with the Paladin, it is probably bad RNG or you have done extras that are not required that have short circuited the event from firing, as you do not need anything other than that to complete the game by that point. My speed runs are run on the GOG releases, so I know it works.