There's a very pretty combinatorial proof of the general identity $$\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$$
for $\omega$ a primitive $r$th root of unity, in Benjamin, Chen, and Kindred, "Sums of Evenly Spaced Binomial Coefficients," Mathematics Magazine 83 (5), pp. 370-373, December 2010.
They show that both sides count the number of closed $n$-walks on $C_r$ beginning at vertex 0, where $C_r$ is the directed cycle on $r$ elements with the addition of a loop at each vertex, and a walk is closed if it ends where it starts.
Left-hand side: In order for an $n$-walk to be closed, it has to take $kr$ forward moves and $n-kr$ stationary moves for some $k$.
Right-hand side: The number of closed walks starting at vertex $j$ is the same regardless of the choice of $j$, and so it suffices to prove that the total number of closed $n$-walks on $C_r$ is $\sum_{j=0}^{r-1} (1+\omega^j)^n.$ For each $n$-walk with initial vertex $j$, assign each forward step a weight of $\omega^j$ and each stationary step a weight of $1$. Define the weight of an $n$-walk itself to be the product of the weights of the steps in the walk. Thus the sum of the weights of all $n$-walks starting at $j$ is $(1+\omega^j)^n$, and $\sum_{j=0}^{r-1} (1+\omega^j)^n$ gives the total weight of all $n$-walks on $C_r$. The open $n$-walks can then be partitioned into orbits such that the sum of the weights of the walks in each orbit is $0$. Thus the open $n$-walks contribute a total of $0$ to the sum $\sum_{j=0}^{r-1} (1+\omega^j)^n$. Since a closed $n$-walk has weight $1$, $\sum_{j=0}^{r-1} (1+\omega^j)^n$ must therefore give the number of closed $n$-walks on $C_r$.
They then make a slight modification of the argument above to give a combinatorial proof of
$$\sum_{k \geq 0} \binom{n}{a+rk} = \frac{1}{r} \sum_{j=0}^{r-1} \omega^{-ja}(1+\omega^j)^n,$$
where $0 \leq a < r$.
Benjamin and Scott, in "Third and Fourth Binomial Coefficients" (Fibonacci Quarterly, 49 (2), pp. 99-101, May 2011) give different combinatorial arguments for the specific cases you're asking about, $\sum_{k \geq 0} \binom{n}{3k}$ and $\sum_{k \geq 0} \binom{n}{4k}$. I prefer the more general argument above, though, so I'll just leave this one as a link and not summarize it.
Here's the full combinatorial argument. Raney's lemma was about half of it, I'd say. The argument shows that $S(n,2) = \binom{3n-1}{n} \frac{3}{3n-1}$ (which is equivalent to the two formulations I give in the question). At the end I'll discuss the generalization to the $r$ case.
Intro.
Consider the sequences with $2n$ occurrences of $-1$ (i.e., $2n$ heads) and $n$ occurrences of $+2$ (i.e., $n$ tails). We want to show that the number of these sequences with all partial sums nonzero is $\binom{3n-1}{n} \frac{3}{3n-1}$. The complete sum and empty sum are clearly $0$, so "partial sum" excludes those two cases. The sequences we want to count can be split into three groups: (1) all partial sums positive, (2) all partial sums negative, (3) some partial sums positive and some negative.
Group 1: The number of these sequences with all partial sums positive is $\binom{3n-1}{n} \frac{1}{3n-1}$.
This is the part that uses Raney's lemma. If all partial sums are positive, the last element in the sequence must be $-1$. Thus we want to count the number of sequences with $2n-1$ occurrences of $-1$ and $n$ occurrences of $+2$ that add to $+1$ and have all partial sums positive. Ignoring the partial sums restriction, there are $\binom{3n-1}{n}$ such sequences. If we partition these $\binom{3n-1}{n}$ sequences into equivalence classes based on cyclic shifts, Raney's lemma says that exactly one sequence in each equivalence class has all partial sums positive. Because there are $3n-1$ elements in each sequence there $3n-1$ sequences with the same set of cyclic shifts, and so there are $3n-1$ sequences in each equivalence class. Thus the number of sequences in Group 1 is $\binom{3n-1}{n} \frac{1}{3n-1}$.
Group 2: The number of these sequences with all partial sums negative is also $\binom{3n-1}{n} \frac{1}{3n-1}$.
To see this, just reverse the sequences counted in Part 1.
Group 3: The number of these sequences with some positive partial sums and some negative partial sums is, yet again, $\binom{3n-1}{n} \frac{1}{3n-1}$.
This one is a little trickier. First, because of the $-1$'s, it is not possible to switch from positive partial sums to negative partial sums. Thus any sequence counted here must have exactly one switch: from negative partial sums to positive partial sums. The switch must occur at some point where the partial sum is $-1$ and the next element is $+2$. Thus we have some sequence $(a_1, \ldots, a_m, +2, a_{m+2}, \ldots, a_n)$ where the sums $a_1, a_1 + a_2, \ldots, a_1 + \ldots + a_m$ are all negative. Consider the sequence $(+2, a_m, \ldots, a_2, a_1, a_{m+2}, \ldots, a_n)$. Since $+2 + a_m + \ldots + a_1 = 1$, and $a_k + a_{k-1} + \ldots + a_1 < 0$ for all $k$, $1 \leq k \leq m$, it must be the case that $+2 + a_m + \cdots + a_{k+1} > 1$ for all $k$, $1 \leq k \leq m-1$. So the sequence $(+2, a_m, \ldots, a_2, a_1, a_{m+2}, \ldots, a_n)$ is in Group 1. To see that this mapping is a bijection, note that any sequence in Group 1 must start with $+2$ and have a first time that a partial sum is equal to $+1$. Thus this transformation is reversible.
Summing up.
Putting Groups 1, 2, and 3 together we see that the total number of sequences we want to count is $\binom{3n-1}{n} \frac{3}{3n-1}$.
Generalization to the $r$ case.
The arguments for Group 1 and Group 2 adapt in a straightforward manner for general $r$; we get $\binom{(r+1)n-1}{n} \frac{1}{(r+1)n-1}$ for both. Sequences in Group 3 can still only switch once - from negative partial sums to positive partial sums. But Group 3 can be broken up into subgroups depending on whether the first partial sum to become positive is $+1, +2, \ldots, r-1$. Using transformations like the one described above for Group 3 in the $r = 2$ case, we can show that there is a bijection between each of these $r-1$ subgroups and Group 1. Thus there are $\binom{(r+1)n-1}{n} \frac{r-1}{(r+1)n-1}$ sequences in Group 3. In total, then, $S(n,r) = \binom{(r+1)n-1}{n} \frac{r+1}{(r+1)n-1}$.
Final comment.
All of this is may be easier to visualize in terms of paths from $(0,0)$ to $((r+1)n,(r+1)n)$ that use right steps of size $1$ and up steps of size $r$ and that do not step on the diagonal except at $(0,0)$ and $((r+1)n,(r+1)n)$. (They can cross the diagonal, though.) I found it easier to discuss the partial sums interpretation, though, given the difficulty of creating such graphics on this forum.
Best Answer
(Sketch of a bijective solution.)
Recall that binomial coefficients count number of walks with steps (+1,+1) and (+1,-1) from the origin to different points (e.g. the number of walks to the point (2n,0) is $\binom{2n}{n}$). Consider the following involution on the set of all such walks: if the path intersects with the line y=l-1 or the line y=-1, reflect its part starting from the first intersection point (w.r.t. corresponding line).
This involution almost gives a bijection between Pn(r mod l) and Pn(-r-2 mod l) (and moving the strip we can get other correspondences of this kind). But it has some fixed points — namely, paths that lie inside the strip 0≤y≤l-2 (aka walks on the path graph of length l-1 mentioned by Qiaochu Yuan).
Now to answer original question one only needs to recall that numbers of such paths for l=5 are exactly Fibonacci numbers.