Although he does end up more overpowered for a large part of his timeline, that is why we are using a version of him from before he becomes overpowered.
You have to remember that neither character would know who they are fighting. Saying that paul would win because he would be able to perfectly predict ezio's movements would require him to have prescience, but we are taking paul before he has prescience. Even if he does gather information about ezio and his methods, I'm not going to accept that he uses a strategy tailored specifically to counter ezio when there are thirty other people he could be fighting.
I'm also going to rule that the shields respect momentum. If you hit a shield user with a massive hammer, for example, although they might not be injured, they would be forced backwards.
The shield provide a visible indication that they are active, as can be seen:
The same visual effect I imagine would alter what the user sees somewhat.
Here's a potential rundown of how I imagine the beginning would be like (it is very open to change, though):
-Paul and ezio enter the island.
-They both start sneaking around the island, paul with his shield active
-Since paul has his senses somewhat altered with the shield, and ezio is a master sneaker, ezio would see the shield, and thus know that it is either paul or duncan he is facing
-Ezio retreats, and tries to set up some sort of trap that would incapacitate a shield user (such as a heavy weight pinning them down)
-once paul comes near the trap, ezio attracts him into coming into approaching
-Paul, upon seeing ezio, uses his prana-bindu techniques and approaches.
-Paul, with his heightened awareness and perceptiveness, avoids the trap and engages ezio
-If ezio can surprise paul by using his hidden blades and grappling, he would win. If not, paul would win.