According to my research you can connect any Pokewalker to any copy of HeatGold or SoulSilver (HG/SS), assuming it is clean and not currently synced to a different save file of HG/SS.
If you do not have a clean Pokewalker (one that is not currently tied to another copy of HG/SS), you can reset it without the original save file on your copy of the game.
Yes, if you go walking with a Pokewalker that has no Pokémon there is a chance that a Pokémon will join you and follow you around. You will be able to import this Pokémon into your game.
The Pokéwalker can be used without a Pokémon stored in it, as well. It
will continue to accumulate steps and watts. The Dowsing Machine can
still be ...
Yep, this is a normal occurrence. According to Bulbapedia,
Pokémon from the route being walked may voluntarily join in the Pokéwalker seemingly at random, taking the spot of the missing Pokémon, essentially being caught for free.
HH/SS were released before region locking was added to DS games so the pokéwalker should work from any country, just make sure you get it in your language
Also it is possible to un region lock your wii so you can play SSBB