When to start seeking PhD positions?
It is never too early to look around for PhD positions. Start out by looking at what is advertised to see what is available and where. If you already know of places to go then get in touch with the department/research group to present yourself. Having a few papers under your belt will be a plus so provide a CV and the papers in your first contact and add a statement of what you want to do and why you are interested in that place.

Being focussed and showing you have a strong urge to continue is likely to impress. 

I can understand it is difficult to say no to two offers and move away but remember that you are free to move. Saying no to a position without funding should not weigh you down. The other position is a little more sensitive of course. But, people move for many reasons, personal and professional. I do not think you need to explain your motives. A change in location is enough. Moving is a positive so there is nothing remarkable about doing so. There is, furthermore, no reason to bring up any negatives about your present location. If your move stirs bad feelings then it is a sign things are not right anyway.