Workaround is to log in to Horizons and pay it off there. Note, you'll spawn wherever your active ship is.
No matter what I tried in Odyssey I could not pay the bounties. I logged into Horizon and was able to pay the bounty.
I didnt had to log in Horizons *() to pay bounties. Not even once.
What i did was to find an IF that was 20+ ly far from any system that had that faction present
In practice - i flew something like 40-50 ly from my current location and payed my bounties.

As i said - zero issues, not even in Colonia (i was based in Tir and payed my more or less accidental bounties in Coeus or Benzaiten)
I basically hate to have to log into Horizon. For reasons.
But i was really tempted to do it for when i did Passenger runs in Robigo.
The EDO Passenger UI is absolutely idiotic, not only it's harder to navigate due to extra nesting, but it's missing crucial information like Cabin type required and the number of seats each VIP requires. We get to see the number of seats after diving in 3 levels in the mission, but the cabin type needed can only be guessed
