Do multiple transitions over the input give finite state machines more power?
Multiple passes do not add any power.

It's possible to do all the passes in parallel, using a state machine whose states are vectors of states in the original machine. Each vector has one element for each state in the original machine, and represents the result of performing the transitions starting at the state corresponding to the position of the element in the vector. A vector state is an accepting state iff there is a path of length $k$ starting at the original machine's starting state and linking the state at each position to that position.

Specifically, let the original machine be $(Σ, Q, q_1, δ, F)$, where $Q = \{q_1, \ldots, q_n\}$. Define the new machine $(Σ, Q^n, q'_s, δ', F')$ with 

$$\begin{align}
q'_s &amp;= \langle q_1, \ldots, q_n\rangle \\
\delta'(\langle q_{i_1},\ldots,q_{i_n}\rangle, s) &amp;= \langle \delta(q_{i_1}, s),\ldots,\delta(q_{i_n}, s)\rangle \\
\langle q_{i_1},\ldots,q_{i_n}\rangle \in F' &amp;\text{ iff } \exists t_1,\ldots,t_k \text{ with } t_1 = 1, q_{t_k} \in F \text{ and } t_j = i_{t_{j-1}} \text{ for } j \in \{2,\ldots,k\}
\end{align}$$
Although that's a lot of states, it's still a finite number, and the set of  accepting states is well-defined and can be enumerated. So the multiple-pass machine is still a finite-state machine.