"cleared' payment means that your bank has approved the payment and it has been received by Paypal.
So if you are paying from your bank balance, there could be up to a 10 day delay for this to happen between the Canadian and US banking systems. It's usually less.
And that does not necessarily release the payment to the seller. If he is new or selling in a high value/high fraud category or has violations on his seller account, the payment may not be released to him for another 21 days. However, this should not concern you since he is still required to ship within 7 days of cleared payment to retain his Seller Protection.
If you are paying from a bank account or from a PP balance, you should be aware that this lessens your level of Buyer Protection.
The best way to pay is with a credit card through PP. This gives you the anonymizing effect of PP, PP's very strong Buyer Protection plus your card's Chargeback protection feature.
And those payments truly are instant.
Hmm.
Another thought. When you are wondering about shipping time, look at the calendar. Victoria Day closed Canada Post on May 21. Memorial Day closed USPS on May 26. And in between was a weekend when less mail ordinarily is moved. Count only business days when the mail is actually moving.