When needing to set a Choice value in a DataVerse entity from Flow, one needs to use the attribute value (the long number) as opposed to the nice label. How to get this dynamically so it does not need to be hardcoded in the Flow?
First, get the entity name and the Choice/Option set name and do a List Rows on the Stringmaps entity.

The filter rows here is :
objecttypecode eq ‘tm_request’ and attributename eq ‘tm_completionstatus’
where tm_request is the entity and tm_completionstatus is the Choice name.
This will create an array, so filter this:

where the From is:
outputs(‘List_Request_Completion_Status_option_set_values’)?[‘body/value’]
and the lower Value is:
item()?[‘value’]
and the Outputs is the label for the Choice.
Then, the attribute value required to update a record (choose custom in the choice drop down) is:
first(body(‘Filter_array_Completion_options’))?[‘AttributeValue’]