This is with POST.
However i have fixed it!.
The Flow was trying to update Navigation to something like /sites/customername/pages/home.aspx
Flow was trying to access that page and failing.
Settting it has the full URL did not work i.e. https://tenant.sharepoint.com/sites/customername/pages/home.aspx
Same Error it would detect it was this tenant and still try to access via only /sites/customername/pages/home.aspx
Finally i solved it by setting the link url to the following:
//tenant.sharepoint.com/sites/customername/pages.home.aspx
This link works in SharePoint and via the API.
Not the best solution but it works!.