I have all of the fulfillment permissions/scopes that are configurable. Much as you had written write_{assigned/merchant_managed/third_party}_fulfillment_orders.
The header X-Shopify-Access-Token is set on my Postman request. The app itself is a Spring Boot application and uses the Base64 encoded : format for the Basic Authorization header. Both give the same 403 response.
"errors": "The api_client does not have the required permission(s)."
The order is unfulfilled, I am able to query 2023-04/fulfillment_orders/<fulfillment_order_id>.json and 2023-04/orders/<order_id>/fulfillment_orders.json and 2023-04/orders/<order_id>/fulfillments.json successfully.