What is an appropriate machine learning technique to analyse development of status over time?
Yes, K-means is an option. But you need to do some data processing first.


My first concern is about quantifying those statuses (are they linearly depended, like does B means something in the middle of A and C)? then numerate them (A to 1 and B to 2 and C to 3 etc)
Represent your data set in a dimensional way, melt years columns into three columns 


Year (with values of 2000, 2001, 2003 etc) so you get a time series dimension.
Year_status (status value).
Year_percentage (percentage of the year).

Try to treat pattern by moving window (kernel), and try different sizes.. for example size of 3 will cluster every 3 followed statuses into patterns centroids (for example.. having a common occurrence of A, E, A)