I understand that Google penalises websites paying for directory listings.
I have a client who has been approached by a couple of companies recently offering a paid listing on their new iPhone App. Would this count against the website and badly affect their Google ranking?

Nope, I don't think so. Google can't crawl mobile apps. Be sure to make clear the conditions, take a look at where the link is placed, and compare with the costs of Google Ads and the like.

Thanks for the advice, it was really helpful

I don't think that google penalize for paid directory submission

With out paid submission you can able to get quality and high pr backlinks paid submission also give you a huge traffic.