I was being silly, of course you can use templates in Automations, so this works:
service: rest_command.todoist
data:
url: sync
payload: >-
commands=[{ "type": "item_complete", "uuid": {{ range(1, 500) | random }},
"args": {"id": "6874471432"} }]
I removed the complete_data, and Todoist uses the current date. I added a random number for uuid, there are probably better ways to generate random numbers, but that’s a start.
You can also probably use templates to facilitate getting the task id, if it’s not completely stable. If you want to complete the same action often, then you will also need some way to “uncomplete”.