Why does replacement {0, 0} /. {a_, -a_} -> c does not work?

To answer the question of "why this does not work?", understand that pattern matching is a structural operation. Let's look at your rule in detail:

{a_, -a_} -> c // FullForm 

Rule[List[Pattern[a, Blank[]], Times[-1, Pattern[a, Blank[]]]], c]

So, in particular, this pattern is looking for an expression with head Times as the second element of a list. The simple number expression 0 does not match that pattern, and so the pair {0, 0} does not match the full pattern.

Semantically, what you want (I assume) is a predicate that asserts that the two elements are additive inverses of each other. And so, on top of the base pattern of a list with two elements, you can add the Condition or PatternTest that other answers demonstrated.

Alternatively, you could avoid naming the elements explicitly by applying a predicate to the pair itself:

{{0, 1}, {0, 0}, {3, -3}, {-4, 4}, {1, 0}} /. {_, _}?(EqualTo[0]@*Total) -> c 

{{0, 1}, c, c, c, {1, 0}}

Or, if you can guarantee that your input is already made up of pairs, then you don't need to check that explicitly:

{{0, 1}, {0, 0}, {3, -3}, {-4, 4}, {1, 0}} /. _List?(EqualTo[0]@*Total) -> c 

{{0, 1}, c, c, c, {1, 0}}

{{0, 0}, {3, -3}, {-4, 4}} /. {a_, b_} /; a + b == 0 -> c 

{{0, 0}, {3, -3}, {-4, 4}} /. _?(First@# == -Last@# &) -> c 

{c, c, c}