Hello,
Can you provide more elements like payment & shipping method configuration screenshot (all will be more usefull, here), because so far we aren't sure to understand the root issue.
Let's explain my idea, in our mind :
- Shipping method only use the shipping address to be restricted by zone => There must be another reason or setting to this result
- Maybe you have in your shipping method zone restrictions => But this won't prevent Payment method to be display, unless for a reason or another, you have set the same restriction.
Awaiting news from you to progress on your subject.
Regards