The payment verified shows you if the client has given their credit card information to UW. If they have, and the card is verified, it will have a checkmark. This means, if you start working on an hourly contract, you will be paid automatically. So you don't have to worry about it.
If their payment is not verified it means that they did not give their card info to UW, and if you start working, there is no guarantee you will get paid.
The stars are the rating that this client has, just like the freelancers get rating from clients.
Sometimes a client is new, and that is why their payment is not verified. Sometimes their card expires, and it's temporarily not verified, until they update it. Sometimes it's a sign that is not a real client, but a scammer.
Make sure to not do any work unless a payment method is verified for an hourly contract, or a milestone is funded for a fixed contract.
Hope that helps!
Marina is correct. I would just like to add that having a verified billing method ensures that clients have a way to pay for the freelancers they hire. This helps fight fraud and keep Upwork a safe place to get to work.