After listening to the detailed description of PayNyms on the podcast, I'm afraid it might not be convenient for the OP project, since it might be a little too expensive, or need trust to a third party to make it cheaper.

It could be convenient for high amount transactions or very sensitive transactions where paying higher fees (due to the use of op_return) might be acceptable for the senders, though.

Let's hope for MWEB...