There are a couple reasons why Paypal (or more generally, any payment service) can know if you've used your card in more than one place, the message that pops up in such cases is - this card is linked to another PayPal account.
Your credit card is absolutely tracked everywhere possible Shouldn't my credit card be stored with a hash under my account only?
If your card is kept hashed then it can be easily compared across accounts. Hashes are deterministic, so for a fixed hashing algorithm a given credit card will always give the same hash. Therefore if they were storing hashes, they could easily compare across accounts and determine if the card was already stored elsewhere. Doing so can be advantageous, as in this case it is being used to prevent fraud (the implication is that if the same card is added to multiple accounts, it is likely due to fraud). Once you have a "secure" hash of a credit card, there's no reason not to check it across different accounts. Paypal certainly can and does.
However, this ability isn't limited to Paypal, and can easily be available to much smaller merchants. For instance with Stripe (a common PCI-compliant payment method) the merchant will be given a unique identifier for each credit card number stored on Stripe. The merchant doesn't keep (or even see) the card number, but they can still compare the given hash against other card hashes that have been used in their systems. This can (and is) easily used for the less-altruistic purpose of tracking a user's buying history across multiple accounts and anonymous transactions, while still maintaining PCI compliance.
So to be clear, your credit card is tracked absolutely everywhere by as many people as can keep their hands on it, even if they don't know your credit card number themselves. Paypal keeps your actual credit card number on file - not just a hash
Smaller merchants can and should make sure and never store, transmit, or even look at actual card details. However, there is no requirement that forbids any merchant from keeping the actual card number if they so desire. In general though any merchant that wants to keep card numbers on file and remain PCI compliant will (theoretically) have to go through stricter validation, security auditing, and effectively have to pay a ton of money in fees. The increased costs and liability of keeping credit card numbers on file while remaining PCI compliant are so large that any moderately well run small-medium business will never try.
However, large businesses can and do choose to do otherwise. The reality is that someone has to store card numbers somewhere so that your card can be billed. The larger credit card processors (which Paypal definitely is) certainly store the full card number. They should store the numbers using strong encryption and secure keys/access control procedures. As for the details of how they actually determine that a credit card number is used twice, ultimately only Paypal can answer that. They may have a method for comparing encrypted card numbers directly, but more likely they also store a hash of the card numbers and compare those directly (h/t Jory Geerts). Either way though, they do keep your card number on file, and they can compare card numbers against accounts.
Note that this doesn't mean that they are "Keeping all registered cards in one big file for cross-reference". Their infrastructure for secure card storage is certainly far more complicated than that. However, they obviously have a compelling business need to be able to compare cards across accounts, and have set up their infrastructure so that they can both store your cards securely and also check for duplicates across accounts. I agree with the linked comment: I would guess that they are also calculating a secure hash of the credit card number and using that for easy comparisons.
