If I understand correctly, REST was formalized by Roy Fielding as a *descriptive* model of the architecture of the web. AFAIK Fielding didn't claim REST was any good, he was just describing the de-facto architecture of the web. The web had already at this point proven an enormous successful distributed hypertext system, so this kind of validates REST as a successful architecture for the domain of distributed hypermedia primarily navigated and consumed by humans.

REST web services was created by applying REST architecture to API's. But is there actually any reason to think REST is a desirable architecture for this domain? More specifically, is there any evidence that say HATEOAS is a beneficial design principle for machine-to-machine communication?

My concern is that HATEOAS makes sense for hypermedia because there are few well-known content types (HTML, images, video etc) and the client knows how to consume them. But for API's the content types are very specific and can only be consumed in a meaningful way by the client if the client is specifically programmed to consume them. Returning an URL to client does not in itself make the client able to consume the indicated resource.