Asset not found error following 'Getting Started'

I am experimenting with the PDF Services API but get stuck on 'Creating a Job'.

Basically, I am following this Getting Started

All (seems) to go well until I have to create the job.

What I've done so far:
1. Get access token
```
curl --location 'https://pdf-services.adobe.io/token' \
--header 'Content-Type: application/x-www-form-urlencoded' \
--data-urlencode 'client_id={{Super Secret Client ID}}' \
--data-urlencode 'client_secret={{Even More Secret Client Secret}}'
```
Since I get a valid response with a dictionary, I get it's ok
```
{"access_token":"hash1234accesshash", "token_type":"bearer","expires_in":86399}
```

2. Get the pre-signed upload uri

```
curl --location --request POST 'https://pdf-services.adobe.io/assets' \
--header 'X-API-Key: {{Placeholder for client_id}}' \
--header 'Authorization: Bearer {{Placeholder for token}}' \
--header 'Content-Type: application/json' \
--data-raw '{
"mediaType": "application/pdf"
}'
```

And now I get an upload URI
```
curl --location -g --request PUT '<insert upload URI>' \
--header 'Content-Type: application/pdf' \
--data-binary '@full/path/to/pdf'
```
I don't get a response so I assume it's done.

Then create the job:
```
curl --location --request POST 'https://pdf-services-ew1.adobe.io/operation/exportpdf' \
> --header 'Authorization: Bearer <that earlier generated access token>' \
> --header 'Content-Type: application/json' \
> --data-raw '{
quote> "assetID": "<that earlier assetID>",
quote> "targetFormat": "docx"
quote> }'
```
And the response is
```
{"error":{"code":"NOT_FOUND","message":"Asset Not Found."}}
```

I tried similar in Python and have generated new credentials. But it's the job creation that seems to fail.
I have based myself on the quickstart guide.

Any ideas where it goes wrong?