This is not an association. It is just a list of key -> value pairs. An association would have head Association and could not have elements with repeating keys. The -> is called a rule (see Rule).

Now to your question. It can be solved with pattern matching.

First, we create functions which test for your criteria:

Clear[startsWith0]
startsWith0[{0 .., ___}] = True;
startsWith0[_] = False;

Clear[startsWith01]
startsWith01[{0 ..., 1, ___}] = True;
startsWith01[_] = False;

.. means repeated one or more times. ... means repeated zero or more times.

Finally we use Cases:

In[35]:= Cases[aa, HoldPattern[key_ -> value_] /; startsWith0[key]]
Out[35]= {{0} -> {1, 2, 3, 4}, {0, 0} -> {2, 4, 6, 8}, {0, 1} -> {5, 
   8, 9, 1}, {0, 0, 0} -> {2, 3, 8, 1}, {0, 0, 1} -> {2, 3, 1, 8}, {0,
    1, 1} -> {8, 2, 1, 7}, {0} -> {1, 2, 3, 4}, {0, 0} -> {2, 4, 6, 
   8}, {0, 1} -> {5, 8, 9, 1}, {0, 0, 0} -> {2, 3, 8, 1}, {0, 0, 
   1} -> {2, 3, 1, 8}, {0, 1, 1} -> {8, 2, 1, 7}}

In[36]:= Cases[aa, HoldPattern[key_ -> value_] /; startsWith01[key]]
Out[36]= {{1} -> {4, 5, 6, 7}, {0, 1} -> {5, 8, 9, 1}, {0, 0, 
   1} -> {2, 3, 1, 8}, {0, 1, 1} -> {8, 2, 1, 7}, {1} -> {4, 5, 6, 
   7}, {0, 1} -> {5, 8, 9, 1}, {0, 0, 1} -> {2, 3, 1, 8}, {0, 1, 
   1} -> {8, 2, 1, 7}}

HoldPattern ensures that the -> is interpreted as part of the pattern (and not as a transformation rule).

Caveat: the pattern 0 matches the integer 0, but does not match the floating-point number 0.0. This will not work if the lists start with 0. instead of 0