For everyone wondering, I fixed it. There is a difference between fulfillment belonging to an order, and fulfilment_orders from an order. There always is an fulfillment_order_id that you can lookup with this endpoint:
https://store.myshopify.com/admin/api/2023-04/orders/{orderid}/fulfillment_orders.json
With that endpoint, you can retrieve the fulfilment_order_id that you can use for the fulfillment endpoint to create a new fulfillment with the order data, tracking number and more.