To answer this question, you should validate different scenarios that users are trying to change the start date:
- By mistake: If a user has already selected start date and end date and noticed they have chosen a wrong start date for their plan, they want to change that to another day, your system must let them to apply this change quickly. The best user experience to handle this state is to automatically adjust the same period. For example, I have selected starting June 10 to 15th but it is a mistake and I want it to be May 10. So I go back, select May 10 for start date, the system should adjust the end date to May 15.
- On purpose: If a user already aware of the action in the first step, but wants to explore more options and tries to restart the process. In this case if you give them some errors, they will be disappointed or confused, they expect that they are able to change those dates as long as they have not finished the process. So in this scenario, they best user experience will be the same.
So I would highly recommend option number 4 which has already passed a lot of good usability tests as well. You can also refer to http://flights.google.com to see a good example for this scenario.