Why can vectorization reduce the use of virtual functions?
Glancing through the paper, it sounds like the answer is as simple as this: 


for "row-based" (non vectorized) operations, the (virtual) functions used to process query results have to be called once per row. 
for "batch-based" (vectorized) operations, the (virtual) functions are called once per batch, and then optimized loops can be run inside the virtual function implementation (reducing virtual function overhead by virtue of just calling those functions less times)


The is mostly covered in the quote you mentioned 


  ...virtual functions implementing block-wise operations handle thousands of tuples per function call...


Calling a function once, to handle thousands of rows, is going to much cheaper than calling the function thousands of times, once for each row.  

In any program, there is overhead to calling functions, especially virtual functions (looking up the actual function implementation's address in a lookup table, missing out on certain compile-time optimizations because the actual implementation function isn't known until runtime, etc - see In C++ why and how are virtual functions slower? for more discussion on virtual function overhead).

Looking to SQL Server's implementation of batch-based query processing (I realize the paper is about HyPer, but the general principles hold), you can find other sources discussing the per-row vs per-batch cost savings in terms of CPU.  Consider this post:

Columnstore Index Performance: BatchMode Execution

It compares row based processing:


  
  Query was executed in ROW mode. The predicate was applied to 3580 rows, one row at a time, to get 1200 qualified rows
  ...The actual CPU cost was 15 ms...
  


To batch based processing:


  
  The query (specifically SCAN operator) was executed in BatchMode. There were two batches, each containing 900 rows, were executed. The predicate was applied to 900 rows at one time
  ...the actual execution time is &lt; 1 ms (the minimal time that can be measured)...
  


Processing query results in batches thus reduces CPU costs in SQL Server for a number of reasons, but virtual function call overhead is likely one of them (although it's probably less significant than, say, operating on compressed data, applying predicates per batch, calculating aggregates per batch, etc).