Hi Max,
BulkEdit is a SharePoint hosted App and so does not require the S2S auth discussed in that thread about Provider hosted apps.
I have tested it personally in a number of environments both on-premise and online and have only seen that specific error message when trying to install in a site collection without Project Server, so can you firstly double check that you are adding it under your /PWA site specifically?
Otherwise have you been able to install other Project apps from the SharePoint app store apart from the Quick Status app you mentioned? Perhaps the Bulk Publish app which is another free Project Server app with identical requirements to Bulk Edit.
Martin