Your contacts on the phone can be stored under different accounts, like your Google account, your Yahoo account, your Facebook account, etc., and these can be synced with those respective accounts (at least the Google ones can--I've never tried it for Yahoo and Facebook). Since they get synced to the cloud, they can be restored easily to your new phone.
Then there's the "Phone Account," which is kind of an anachronism, and I wish it would just go away, because it tends to lead people to lose their contacts unwittingly. Before people could easily sync their Contacts with various cloud accounts, we all had to store our contacts directly on the phone, hence the "Phone Account." These contacts were stored in the phone's memory (and usually on the SIM card, if present), but the only way you could back them up in the old days was to sync them with Microsoft Outlook or some other desktop PIM using proprietary software like HTC Sync. Or you could pay your cellphone company an unreasonable amount to have them backup your contacts with their own server. Now that everyone has some kind of Google or Yahoo or Outlook.com account, no one really needs a Phone Account any more, but it remains, and people still unwittingly enter contacts into it. Any contacts in the Phone Account can't be synced with your Google account, and those contacts will be lost if you change phones and didn't remember to backup or transfer those contacts somewhere else.
To change all of your Phone Account contacts to Google, you'll need to export them first, then import them into the Google account. I think you can do this all on your phone, but not sure since I've never done it myself. On my Razr Maxx, this is how you'd do it:
1. Open the People or Contacts app.
2. Tap Menu, then "Contacts to Display." Select your Phone Account.
3. Tap Menu, then "Import/Export." Select "Export to storage."
4. When it is done exporting, tap Menu, then "Import/Export," then "Import from storage."
5. Choose the file you just exported, and select your Google account as the destination. (After step 3, it might be necessary to change your Contacts to Display to your Google account.)
Your Phone contacts should now be in your Google account, and will then be synced to the cloud.
"Starred in Android" contacts are the ones you make Favorites in your phone's dialer.