« Tourner à gauche » et « tourner à droite » sont justes. C’est utiliser l’imparfait du verbe devoir qui pose des problèmes. Si l’on est toujours dans la voiture et on a fait une faute à une intersection, le conducteur peut dire :

• J’aurais dû tourner à gauche, mais […j’étais dans les nuages]. C’est la circulation, maintenant on roule plus vite que prévu.

• J’aurais dû prendre cette voie-là au lieu d’aller tout droit. Pardon, je ne l’ai pas fait exprès.

• J’aurais dû prendre la voie là où on vient de passer mais….

C’est le conditionnel passé. Cela exprime "I should have [turned/gone/done]" en anglais.

La première formulation est une possibilité correcte et peut-être bien la meilleure.

• Je devais tourner à gauche, mais cela m’est sorti de l’esprit.

La seconde est aussi correcte mais la référence à la voie doit apparaitre dans le contexte.

• Je devais prendre une voie que l’on vient de passer mais, par inadvertance, je suis allé tout droit. (par exemple)

Dans la troisième option, la référence de « cette » n’est pas clairement « la voie utilisée » et il vaut mieux changer cela et dire « et j’ai continué tout droit ».

• Je devais emprunter la voie devant laquelle on vient de passer, mais en raison d’une distraction, j’ai continué tout droit.

« Tourner à gauche » et « tourner à droite », pour répéter ce qui a été dit dans la réponse de user livresque, est tout à fait correct. Ce qui n’est pas correct c’est « tourner sur une rue » ; on ne dit que « tourner dans une rue /dans la rue X » (ngram).

« Sur » est cependant utilisé avec les indications de sens « gauche » et « droite » lorsque l’article défini est utilisé. Sans l’article on utilise à.

• tourner sur la gauche, tourner sur la droite