Do I need to disable iCloud Storage Plan to change iTunes store?
Well, I contacted Apple Support, and they told me this:


  If you have an iCloud Storage subscription, you need to downgrade your
  active storage subscription to its original before you change your
  country or region.


So I did.

However, I am not sure if it was really necessary (because there was no red label about this in country settings like it was with Apple Music), but I didn't want to sacrifice one more month of waiting for that experiment. This is why I don't mark this answer as an accepted solution for the original question.