RecurrenceTable not evaluated: mathematica just echoes input

As far as I can see with a quick look, you system is overdetermined.
You have to leave out s1[0, k] == 1

RecurrenceTable[
  {
   s1[n, k] == s1[-1 + n, -1 + k] + s1[n, -1 + k],
   s1[n, 0] == Boole[n == 0],
   s1[n, 1] == Boole[n <= 2]
   }, s1, {n, 0, 6}, {k, 0, 4}] // Grid

(*
1   1   1   1   1
0   1   2   3   4
0   0   1   3   6
0   0   0   1   4
0   0   0   0   1
0   0   0   0   0
0   0   0   0   0
*)

You are not doing anything wrong. Mathematica is attempting to solve the recurrence equations and, apparently, failing.

If what you want is to construct the table, you can do so by explicitly coding the recursive definition as follows (this is inefficient, and one can speed it up in any of several different ways):

ClearAll[s1];
s1[0, k_] := 1;
s1[n_, 0] := Boole[n \[Equal] 0];
s1[n_, 1] := Boole[n \[LessEqual] 2];
s1[n_, k_] := s1[n, k] = s1[n - 1, k - 1] + s1[n, k - 1]

(I hope I did not transcribe anything wrong). Notice the memoization in the last line which speeds things up quite a bit, as well as preventing recursion from getting too deep.

The table is then easy to produce:

Table[s1[n, k], {n, 0, 6}, {k, 0, 4}] // Grid

(I have no idea if this is correct; if not, I have transcribed the definition incorrectly).

In summary, one must make a distinction between explicitly evaluating the recurrence relations (as I do here) and attempting to "solve" the recurrence relations. This distinction is similar to that between Total@Table[f[i],{i,1,10}] (which produces a bunch of numbers, if f is defined, and then adds them up), and Sum[f[i],{i,1,10}], which attempts to perform a much more sophisticated operation. Another way to view this is as a distinction between mathematics and programming; mathematically, one is just producing a table of these values defined by a recurrence relation; but in terms of what is going on, RecurrenceTable is apparently trying to do something rather sophisticate (and, it seems, failing), while what I do is carrying out the definition of the recurrence literally and with specific numbers until it bottoms out.

There is an available-on-request package Guess.m that can solve some recurrence relations that Mathematica natively cannot. I suggest you give it a try if you do this kind of thing often.