Turning the tables
Another day and some progress has been made! I found my way from Khal to Lomshir where there are more guards with lower rank to parley with. Although their hands were arguably still too good for their level I did manage to find one I could beat … and beat him I did. This enabled me to finish my quest at last. As a reward I was given a baton which grants Noble presence. Not enough to talk to the nobleman in my other quest but enough to get started.
Aside from that I spent some time exploring and got my third "You are the first to discover this area" message. In quite a cool place too. The Coward’s Plunge is the name, I think (going from memory), of a nice coastal cave system.
Then I went a bit too far and got wtfpwned by a level 38 hyena thing. Oh well.