I’m having the same issue.
I just rolledback from API version 2023-04 to 2023-01 and it works.
So using PUT to themes gives 404 for the 2023-04 version.
I also tried the new API version 2023-07 which also gives 404.
I can’t find any difference in the API documentation, except scopes which I have (and if that was the case should a 401 be returned instead of a 404).
Have you identified the issue?