Just go to .../qa-include/qa-lang-main.php and change in line 49 the term:
'all_categories' => 'All categories',
into
'all_categories' => 'Your desired title',
Thats it.
To change the titles design You can refer in the css file to:
.qa-nav-cat-all {}