To get Paul, first you must have completed the Rat Cave Quest with Algernon. The other requirement is to have sealed on of the Abyss Gates. Now return to Nina's house in Kidlanto, and you'll meet Paul there. If you had cleared the Thieves's Den, you might have seen Paul there too.
Paul is pretty good with the Bow and also has some pretty nice strength. He seems to survive alot more than anyone else that specializes in the Bow.