REST API: does securing the first call with a CAPTCHA make sense?

The standard approach to this would be to e-mail the user to confirm the account and if this doesn't occur in a pre-defined period of time, to delete the registration.

You could combine this with some Anomaly detection so for example if you got large numbers of registrations from a single IP address you could assume that this is hostile and block that IP address. Not perfect against a determined attacker but could deter less determined ones.

You could also add something like a CAPTCHA to the registration process, again this could deter less determined attackers but there are a number of ways round these, such as CAPTCHA completion services which are relatively inexpensive, so a determined attacker could bypass them.

Which of these are reasonable largely depends on the risk/threat profile of your application.