There are two reasons why a self-service flow will not trigger, besides the editing permission in the All People - Own’s data permission group.
1. If the user editing their profile is an Admin. Admins have the highest level of access in the system, which means self-service flows are not applicable to them.
2. If a user has elevated permissions. If the user is part of a custom permissions group that gives the user access to edit the category included in the self-service flow, for other employees, this applies to the user themselves.
In this case, you will have to ensure that the user actioning the self-service is removed from the applies to of the custom group. With this change, the permissions in that group will not apply to the user and the self-service should trigger for them.