無くしてしまったのは過去のことなので、lostとなり、英語では、何を持っていないのかはっきりと言わなければならないので、
Paul lost his cell-phone and does not have one now.
が自然な表現となります。
ここではoneで前に述べられたcell-phoneを指し、hisで誰のcell-phoneかをはっきりとさせています。