If you're using Common Data Service (current environment) connector in your flow and getting the following errors, that means you are either

  1. setting the GUID value directly or
  2. not providing a correct plural version of entity schema name.

Empty segment encountered in request URL. Please make sure that a valid request URL is specified.
Resource not found for the segment xxxxx
1. In (classic) Common Data Service connector, you can just set the GUID value of the record to populate the lookup value of the field. For polymorphic lookups, you will have an additional Type dropdown field (e.g. Customer Type) to choose the entity type of the record that you are setting.

But in the new CDS (current environment) connector, you need to provide the type of entity even if the lookup is just normal lookup to a single entity. For polymorphic lookups, there will be multiple fields for each entity type (e.g. Customer (Accounts) and Customer (Contacts) ) and you need to fill up the correct entity type that you are trying to populate. (and you still need to provide the entity type). Imagine if you are creating one of the activity records (e.g. Task) in the environment with a lot of entities enabled for Activities, you will see a lot of Regarding (xxxxxx) fields in your flow step.

2. Don't be fooled by the plural display name of the entity which is shown beside the field label. The EntitySetName that you need to provide is case sensitive and you cannot use that plural display name (Contacts) or entity logical name (contact). As mentioned in Dynamics CRM Tip of the Day #1311, what you need to use is the plural version of the entity schemaname (aka EntitySetName) followed by the GUID enclosed in parentheses. <>(<>)
e.g. contacts()

For out of the box entities, the EntitySetName is the same as the plural display name for most of them. But things get tricky when you are trying to populate the value for the custom entity. You may be able to add 's', 'es', 'ies', etc. but how the system defines the EntitySetName is not perfect for all scenarios. (e.g. the EntitySetName of my lzw_journey entity is lzw_journeies)

In order to get the so-called EntitySetName, you can either search from
[Organization URI]/api/data/v9.1
e.g. https://contoso.crm.dynamics.com/api/data/v9.1

or replace the <> in the following URL format to get it for a particular entity
[Organization URI]/api/data/v9.1/EntityDefinitions(LogicalName='<>')?$select=EntitySetName
e.g. https://contoso.crm.dynamics.com/api/data/v9.1/EntityDefinitions(LogicalName='contact')?$select=EntitySetName

Now that we have to provide the EntitySetName to set the value, I am not sure how to set the null value or set the optional lookup value from another record which can potentially be empty.
When I set the null value from the Expression, I get the following error.

An error occurred while validating input parameters: Microsoft.OData.ODataException: The 'odata.bind' instance or property annotation has a null value. In OData, the 'odata.bind' instance or property annotation must have a non-null string value.
The error message is the same as setting null for single-valued navigation property using Xrm.WebApi but I am not sure it is possible/necessary to use a DELETE request to remove a reference to an entity as mentioned in the Microsoft documentation.

If you have a solution for that, please leave a comment below. For now, I changed it to the (classic) CDS connector for those scenarios.