The data upload/download step you mentioned from PS3 to PS4 is for secondary data like hotbar setup, gearsets, etc. You should have your characters available regardless, so long as you're logging into the same account from both platforms.

Simplest possible problem: Did you look in the right place? Characters only exist on one home server. The Coeurl server is in the Aether data center, so on the screen that lets you select a Data Center, you should select Aether. Then when you choose Start, it will bring up the character selection/creation screen for Aether worlds. Go to the world selection button near the top right of that screen, and choose Coeurl. Once you're on the right data center and world, it should show your character.