PAXARO. Metaphoricamente se toma por astúto, sagaz y cauteloso, con alusión al gorrión, que se juzga el más astúto de las aves. Latín. Sagax. Callidus. —RAE, Diccionario de autoridades, tomo V (1737)
Si bien la astucia, la sagacidad y la cautela no son de por sí cualidades negativas; sí que son cualidades necesarias para ser un pícaro y salir airoso. Con sentido negativo ya se recoge como mínimo en el siglo XIX:
Hombre de cuenta ó pájaro de cuenta: El reo de gran cuidado o a algún facineroso terrible. —Roque Barcia, 1880
PD: Debo confesar, puesto que no soy un pájaro, que todo este trabajo de documentación lo ha hecho un escritor llamado Arturo Ortega Morán, y yo me he limitado a coger los extractos relevantes de la entrada correspondiente de su blog, que recomiendo visitar para saber qué significa «de cuenta».