According to the documentation, RecordStore uses an incrementing counter for producing the record ID-s. Based on that you can simply check if the number of records is greater than 10, enumerate the records and delete the one with the lowest ID.
Something like
Code:
while(rs.getNumRecords()>10)
{
    int delid=rs.getNextRecordID(); // or just Integer.MAX_VALUE
    RecordEnumeration re=rs.enumerateRecords(null,null,false);
    while(re.hasNextElement())
    {
        int id=re.nextRecordId();
        if(id<delid)delid=id;
    }
    re.destroy();
    rs.deleteRecord(delid);
}