Правильно: «Степан и Максим уже немного устали от путешествия.»

Кратко почему:

Имена: «Максим» с заглавной буквы.Согласование: при двух лицах прош. время — мн. число «устали», а не «устал».Падеж: после «от» — родительный, поэтому «путешествия».