Jutfrank -- I think my Canadian ears are caught between the British and American usage. "Can have done" is certainly not something you hear every day in Canada. It gives off a literary air, a phrase a fastidious writer might use -- or, indeed, something redolent of imagined British middle class afternoon tea. But it's not wrong or in any way weird, and once you start thinking about it, it's easy to draw the semantic distinctions I've outlined above.
But Canadian English is a funny thing. It sounds perfectly broadcast-American, but it isn't. A smattering of native vocabulary aside (chesterfield, hoser, keener, or two-four, as in "two-fours on May two-four"), I think in many ways it maintains the old-fashioned imperial usages of c. 1900. Look at our spelling, for example: always colour and centre, but also always realize. And the more polished our language, the more old-British it becomes. Until about 1990, our CBC radio news were delivered with an RP-like pronunciation called "Canadian dainty", and certainly even in the 1970s all schooling strongly emphasized the imperial/Commonwealth past.
I know that's a long digression to explain why I've said that this phrase is "cultivated -- or regional". :-D
All the suggested replacements are fine as well, really.