should one worry about timing attacks with signature verification? To compare two varablies in such a way that timing attacks don't exist it's generally recommended you pad the strings to the same length and then look at each byte, even if an earlier byte was different.

In ECDSA and DSA you compare $r$ to some value to see if the signature is valid. But I'm thinking that there's no need to do a timing insensitive equality test because, with signature verification, you're using all publicly available information anyway?
Correct.  In fact, often—and pretty much always for their modern cousin EdDSA—the verification procedure is implemented with variable-time operations, because there are no secrets involved.

However, you may wish to take care in case you rely on key privacy anywhere in your protocol.  The paper is presented in the public-key encryption setting (distinguishing ciphertexts under one unknown key from ciphertexts under a distinct but also unknown key), which is straightforward to transfer to the public-key signature setting (distinguishing signatures under one unknown key from those under another)—but maybe the adversary in your case wants to learn which public key you're verifying signatures of, and does so by probing how long it takes to compute a rejection with various different signatures.  It's a stretch—and maybe it's actually moot for some reason that I haven't thought of—but I'm not aware of any research on that specific question.