You probably need to ask a lawyer to be sure; I am not a lawyer, so take what I say with a grain of salt. You can almost certainly find a lawyer to advise you on this matter for less than $16,000, so that seems like a good investment to me.
For reference, this is the COPPA law and these are the FTC's FAQs on compliance. This is the source of most of my conjecture, below, but you should read them both yourself.
First, Google Play's legal terms prevent users under 13 from using the service.
Age Restrictions. In order to use Google Play you must be 13 years of
age or older.
So legally, no such user can be directly accessing your application anyway. However, you probably still want to protect yourself from a child who illegally or indirectly accesses your application. COPPA does not require you to investigate the age of users, and it does not require you to offer your services to users under 13, so you can, like Google Play, simply block them from participating via your own EULA. However COPPA does not permit you to block them if your game is targeted to that audience. Thus, you should avoid explicitly targeting that audience. It's probably the safest option, because you don't have "actual knowledge" that a user is under 13.
What constitutes "targeting" that audience (making your app "child-directed," see the FAQs) is fuzzy, so perhaps you can't (or just won't) explicitly exclude or block them. In that case, you need to be aware that even a unique identifier suitable for tracking achievements is considered "personal information."
(7) A persistent identifier that can be used to recognize a user over
time and across different Web sites or online services. Such
persistent identifier includes, but is not limited to, a customer
number held in a cookie, an Internet Protocol (IP) address, a
processor or device serial number, or unique device identifier;
Fortunately, you may be covered by the exception to requiring parental consent
(c) Exceptions to prior parental consent. Verifiable parental consent
is required prior to any collection, use, or disclosure of personal
information from a child except as set forth in this paragraph:
(7) Where an operator collects a persistent identifier and no other
personal information and such identifier is used for the sole purpose
of providing support for the internal operations of the Web site or
online service. In such case, there also shall be no obligation to
provide notice under §312.4;
So the tl;dr is:
- don't put yourself in a scenario where you have actual knowledge that a user is under 13
- if you just collect an identifier and only use it to drive your achievements, you're probably okay
- ask a lawyer, because I'm just some guy on the internet who doesn't mind reading legal documents now and then and could be missing something very important