I don't know why [my personal data] is needed anyway, considering it is not a CD game, but downloadable one.
Yeah, since it's a totally digital transaction info such as your mailing address isn't necessary. But when you registered your PayPal account you had to provide an address and phone number then, so it makes sense that if you enter fictitious info when ordering Machinarium PayPal assumes that someone else is attempting to use your account without your knowledge.
If it's total anonymity you want then consider establishing a mail drop for yourself like
this or
this.