Replace the K2 Router in /components/com_k2/router.php with the previous version from:
jmp.sh/CZ2oMKG
Enable Advanced SEF again and adjust your category path.
You should get what you want.
The new router in v2.10.3 needs some "polishing" so the functionality of both URL routers will be merged in the next update of K2.