The Sprint Planning is done and, in the middle of the Sprint, the priority changed. Because of the priority change, the story needs to move to a future Sprint.

This is not adding new stories, this is removing the planned stories.

The story is not yet started. Is this a good practice?

Two thoughts:

1. Since the story is not started, it can be moved.
2. The story is planned, estimated and tasks and hours were allocated. The story can be blocked and carried forward to future Sprints. This can help in finding the number of times stories are pushed.