TL:DR
Yes, it is perfectly fine to remove a story due to changing priorities and move it back into the Product Backlog, ready for a future sprint.
Why is it fine?
A Scrum Team can do several things as per the Scrum Guide
The Sprint Backlog is updated throughout the Sprint as more is
learned. It should have enough detail that they can inspect their
progress in the Daily Scrum
and
The Sprint Goal is created during the Sprint Planning event and then
added to the Sprint Backlog. As the Developers work during the Sprint,
they keep the Sprint Goal in mind. If the work turns out to be
different than they expected, they collaborate with the Product Owner
to negotiate the scope of the Sprint Backlog within the Sprint without
affecting the Sprint Goal.
and
Through discussion with the Product Owner, the Developers select items
from the Product Backlog to include in the current Sprint. The Scrum
Team may refine these items during this process, which increases
understanding and confidence.
A team can be both add to and remove items from the Sprint Backlog and also negotiate with the Product Owner to add to and remove items from the Product Backlog.
Other Considerations
Whilst the Scrum Guide gives you permission to do so, it is worth exploring with the team why the situation arose. Some sample questions you may be interested in include
- Why did the priority change?
- Where did the priority change come from? Was it driven by the team?
- Was the story critical to the Sprint Goal?
- Is the Sprint Goal still achievable?
- Did the story have an engineering dependency that we missed?
- Is the story still required?
A careful analysis of the events surrounding the removal of the story may yield interesting insights which help you improve the environment of the team