Besides すみません are there other ways to say "Excuse me" in Japanese? Is すみません the most formal way of saying this?

See a translation

Unlike English, you have plenty of different ways for begging pardon in Japanese. Here are from the most formal to the most informal (let's say rude :) ).
申し訳ございません (もうしわけございません) is the most formal expression for begging pardon you'll find in Japanese. It is usually used with customers or the big boss if you made a terrible mistake. It would sound weird if you use it with strangers.
申し訳ありません (もうしわけありません). Same as above but softer
失礼します (しつれいします) Sounds more natural, and still polite
すみません The basic
ごめなさい Usually used by elders toward young people. Or someone you're close with
ごめん
すまない
わるい Unless you hate that guy or he's your bestfriend, do not use that one. It sounds like you absolutely don't care ;)
You have plenty others with tense declinations, context etc... Hope you will find your way through Japanese !