Si POO nació con Java, que paradigma usaban antes, por ejemplo en C?

Procedural y funcional

Aquí puedes ver una línea de tiempo que explica más o menos la evolución de los paradigmas de programación.

Ohh ya veo, entonces fue Java el que nació de POO

LA POO no nació en JAVA, realmente tiene origen en un lenguaje de simulaciones llamado Simula 67, tiempo después los conceptos fueron refinados en Smalltalk.

la programación orientada a objetos tuvo un auge con C++ en los 80, que es una extensión de C, pero bajo otro paradigma. C sigue es de paradigma Imperativo.

Poo nacio con smalltalk, el paradigma de c es lenguaje imperativo