Efficient SELECT for array of tuples in PostgreSQL
If you aren't fixed on the array input, you can use a tuple comparison. 

select *
from records
where (id, updated) in ( (1, timestamp '2019-01-01 00:00:00'),
                         (2, timestamp '2019-01-02 00:00:00') )


That can make use of a regular btree index on (id, updated)

Note that this uses = for both values and is equivalent to 

where (id = 1 and updated = timestamp '2019-01-01 00:00:00')
   or (id = 2 and updated = timestamp '2019-01-02 00:00:00')


But you want to compare the timestamps using &gt;. You can do that if you join against a values clause:

select r.*
from records r
  join (
    values 
       (1, timestamp '2019-01-01 00:00:00'),
       (2, timestamp '2019-01-02 00:00:00') 
  ) as t(id,upd) on  r.id = t.id
where r.updated &gt; t.upd;


Online example: https://rextester.com/GGC83046