How to get multiple multirows in a table?

I believe your problem is that you didn't put enough empty cells for the following lines. A multirow will allow content to occupy space, but doesn't actually create the cells that are under it. I rewrote your code aligning everything to illustrate that.

\begin{tabular}{l r | l || r r}
Vzorka & Výskyty & Algoritmus & Porovnania & Prístupy \\ \hline 
\multirow{5}{*}{Gabriel} & \multirow{5}{*}{8} & NAIVE BINARY          & 158   & 44 \\
                         &                    & NAIVE BINARY_LCP      & 174   & 92 \\
                         &                    & NAIVE INTERPOLATION   & 168   & 78 \\
                         &                    & LESS NAIVE BINARY     & 98    & 26 \\
                         &                    & LESS NAIVE BINARY_LCP & 124   & 58 \\ \hline
\end{tabular}