I'd like to move a document to another partition by changing the partition key. I have read somewhere that the document would have to be deleted first and a new one with the new partition key would have to be created. If that's the case, can this transaction be atomic? In other words, is it possible to execute a transaction across two partitions and rollback if one update/write operation fails?
No, this operation is not transactional.
As you probably know the partition key is immutable and cannot change, that's why you need to delete it first and then recreate it with a different value.
Using a stored procedure, which support transactions, is out of the picture because they can only operate against a single partition. This means that you need two of them in order to do your delete/create, which in return means that it's no longer transcriptional.
What you can do to "cheat" is to save the document you're deleting in memory, then do the delete operation and check the response to see if the document was successfully deleted. If it was then move on with the creation of the new one and check the creation response. If it was created successfully, then you're happy. If, either the delete or the create fails, then recreate the in memory document. However this also have the risk of the created document failing to be recreated, but it's the closest thing you have in order to imitate this behaviour.