So, ultimately I ended up using GPT-4 to help me out and this is the solution I found:
Instead of calculating velocity and rotation on the client and passing it to the server I now only pass player input (on tick) and handle calculations server-side. While the Velocity variable isn’t itself replicated, the rest of the CharacterMovement component is, so I can simply set it on the server and let CMC handle replication. Rotation on the other hand has to be set client-side.
Movement is smooth as you’d expect from CMC, but rotation is choppy so I plan to implement client-side prediction algorithm at some point in the future. At least it’s playable now!