The adjective ψευδώνυμος “falsely called” is good classical Greek, so one would expect the corresponding noun to be *ψευδώνυμα*ψευδώνυμον (neuter) “a false name”, and as such borrowable into Latin.
The Oxford English Dictionary traces “the Latinate form” pseudonymus to the 17th century.