jernejmramor → created an issue.
I've tried replicating this issue again by creating a new custom module which adds an Entity that extended EntityChangedInterface, and exposed a rest endpoint with custom rest resource plugin that extended EntityResource. Using postman API I then created a new entity using POST method, and updated the same entity with PATCH method. Every successful update of an entity is also reflected in updated 'changed' value in the database.
I've also tried replicating this behavior using bundle-able custom entities and even then 'changed' value was always updated in database as expected.
If this is still an issue, please provide a more detailed set of replication steps so that we can provide tests and solution for this issue. I'm committing an updated patch form what is currently in the open MR so that plugin uses DI for the time service. I'm also changing the status to Postponed (maintainer needs more info) as the issue is 4 years old, and is no longer replicate-able (at least by me).