I had the same issue with "URL was not parsed due to an ODataUnrecognizedPathException. Resource not found for the segment provided in the URL." when trying to write a D365 OpportunityProduct line.
I saw that the errors in PowerAutomate (when inspecting the inbound and outbound values of the action) has @OData bind in the URL path (see your Power Automate Action's runtime/error JSON fragment of what it is trying to do). This is how this issue came around and gave me a clue that this special format of adding EntityReferences was needed rather than dropping the fields in directly (as normally works).
My Flow was just adding the field names in the boxes and expecting PowerAutomate should be able to see that it is a reference field and bind it accordingly but no, it would seem extra work is needed.
For reference, I added the same steps in LogicApps and it could deal with the binding no issue and knew how to bind a lookup.
Erroring Flow vs working LogicApp.

And the values which surface upon run are the same...

I have wasted hours on this issue and I think it could have been clearer (as well as the error message). I also thought the point of PowerAutomate was that developer things were not needed, it was available to all.
I wonder if the development team missed checking if the field was a reference field from the outset and can't fix it retrospectively for fear of breaking existing flows.
So my solution in PowerAutomate was to add the three required fields as follows:

Of course you can drop the field value in the field rather than the raw GUID text, this also works...
e.g.

Use the ...(Value) field to get to the GUID.

(Which has _ and value in the name suggesting it is a lookup/reference field
)
If you want to see the plural name of D365 entities to use in your flows
https://yourinstancename.crmX.dynamics.com/api/data/v9.1
(change the base path and version v9.1 accordingly but CRM online should be v9.1 version and above).
You may get use from this also, to find out more detail about the entities in your system:
https://yourinstancename.crmX.dynamics.com/api/data/v9.1/EntityDefinitions

With the entity definition looked up I take the GUID (MetadataID) from the entity definition in I'm interested and put it into the following between the () as per this example.
https://yourinstancename.crmX.dynamics.com/api/data/v9.1/EntityDefinitions(5f2e7ae7-d327-49b5-a343-61d48f1bcd28)?$expand=Attributes so I can find out more about the fields for the entity. For this expand the Attributes node of the returned JSON and you will see the fields and their type.