I have just started watching a movie or I have just started to watch a movie

This is correct and common in British English.

I just started watching a movie or I just started to watch a movie

This is correct and more common in American English.

Grammatically, just wants the present perfect in British English, no matter what.

In American English, you can use it with the past tense.

The verb start can be followed by both the infinitive and the ing form.

You can use both the present perfect and the past tense for the reasons I mentioned.

I don't <em>completely</em> agree with Clara or Iris. The right way is "I just started watching a movie" or "I've just started watching a movie". Both those ways work.

There are a couple discussions on using have and skipping it: http://forum.wordreference.com/threads/ive-just-started-vs-i-just-started.2715831/

The correct way is:  I have just started watching a movie.  

The reason is because the verb needs to be in present perfect tense.  

I just start watching a movie.

or

I just started watching movie. 

oh ya, I forgot to add "a" in front of "movie".

I just started watching a movie.