SQL doesn't by default have an "order" to return your result set by.  So when you issue a command like "SELECT Transaction_Date FROM Employee_Change", depending on various factors, you could get it in the order you expect, or it could be all jumbled up.  Same thing applies when you do an update like that.

What I would do first is change your update into a select.  This will give you an idea of what it is actually doing and I expect it is not what you think it is doing.  When I did that, instead of getting 5 rows, I got 15.
So your logic is wrong with the join.  This is easy to see as when the date is 1.1.2017, there are 4 rows which are greater than it so that part of the join will give you 4 rows.

So what I think you will want to do is something like this:
WITH cte AS
(
SELECT [Staff_ID] ,
     [Transaction_date] ,
     [Staff_name] ,
     [old_store] ,
     [new_store],
     ROW_NUMBER() OVER (partition BY Staff_id ORDER BY Transaction_Date) AS [rn]
FROM Employee_Change
)
UPDATE [cte1]
SET [cte1].[New_Store] = [cte2].[Old_Store]
FROM cte cte1
FULL OUTER JOIN cte cte2 ON [cte1].[rn] = [cte2].[rn] + 1

I'd recommend doing a "begin transaction" and "rollback transaction" before doing the update though with selects inbetween so you can verify the data.