Solution:

We will show that the least value of $n$ is $n=13$.
If $n \leq 12$, Bob wins by painting black the 4 rows containing the highest numbers of red cells. Indeed, if at least 5 red cells remain, then one of the rows not blackened contains at least 2 red cells. Thus, each one of the rows blackened contained at least 2 red cells, and then all blackened cells were at least 8. However, in this case, at most 4 would be not blackened, a contradiction. It follows that at most 4 red cells remain which can be easily blackened by Bob choosing the 4 columns that they are in.

Now let $n=13$. Enumerate the rows and the columns from 1 to 8 and each field will be referred to by the pair (row,column) it is in. Let Alice paint in red the fields
$$(1,1),(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(5,5),(6,6),(7,7),(8,8)$$
as in the following figure.

Suppose that Bob has managed to paint all red fields in black. The cells $(6,6),(7,7),(8,8)$ are painted black by three different lines (rows or columns) containing no other red felds, so the remaining 10 red fields have to be painted black by the remaining 5 lines. As no line contains more than 2 red fields, each red field has to be contained in exactly one of these lines. Assume that $(1,1)$ is painted black by a row, that is, row 1 is painted black. Let $k$ be the least positive integer such that row $k$ has not been painted black, where $2 \leq k \leq 5$. Then field $(k, k-1)$ should be painted black by column $k-1$. However, in this column there is another red field $(j, k-1)$ contained in the painted row with number $j<k$, which is a contradiction. Similar reasoning works if $(1,1)$ is painted black by a column.