SQL: Search for a keyword in several columns of a table
Something "prettier"? And so many repetitions call for generalization?  

SELECT *
FROM   tabela AS t
JOIN   "TabelaPai" tp ON tp."ID" = t."RefTabelaPai"
WHERE  NOT t."Deleted" 
AND    tp."RefProject" = 'projectid'
AND    t::text LIKE E'%\\_\\_param1\\_\\_%';

Major points:


You can reference the composite type of any relation in the SELECT list. I quote the manual:


  Whenever you create a table, a composite type is also automatically
  created, with the same name as the table, to represent the table's row type.


You can cast the whole row (the composite type) to its text representation in one fell swoop, which is a very convenient syntactical shorthand. The resulting filter in my query is guaranteed to find every occurrence in the whole row.
The LIKE operator is generally faster than regular expression pattern matching (~). Regular expressions are far more powerful, but whenever LIKE can do the job use it. Its syntax is simpler, too.
Underscores (_) have a special meaning for the LIKE operator, so you need to escape literal _. Default escape character is \, which also has a special meaning in escape string constants, so you have to double them when you use the E'' prefix: E'\\_'.

As of version 9.1, the setting standard_conforming_strings is on by default. With this setting \ has no special meaning in plain string literals (without the E prefix) and you don't need to double them: '\_'.
There is a minor flaw / corner case: If the separator in text representation (, by default, and some values are enclosed in double quotes "), can be part of the search pattern, there can be false positives.


Minor cleanup / simplification:


JOIN is shorthand for INNER JOIN.
It is cleaner to write AND tp."RefProject" = 'projectid' as WHERE clause, as it has no connection to tabela. Else you could put NOT t."Deleted" into the JOIN condition as well. Either way, you get the same result here.
No point for mixed case in Tabela (without double quotes). By default (and without double-quotes), all identifiers are folded to lower case automatically. My standing advice is to use legal. lower case identifiers exclusively in PostgreSQL and avoid avoid double-quoting and possible confusion.