It's been a while since I last played, but I remember with Credos you had to complete an objective in order to get a point. If you didn't like said objective, you'd have to abandon it (and lose a point) in hopes of getting a better quest.
So how about giving credo quests multiple options to complete it and get the point?
For example:
Wave to Bark-Barky Tree.
OR
Tame a cow.
Wave to Barky-Bark-Face.
Tame a cow OR boar.
Fish a cat fish.
Completing either or will award you the point.
In an open world game of this size, you shouldn't be so restrained, there should be a degree of freedom and options to pick from.