I am running a same query on a same copy of the database on a
Azure SQL (Tier S3) and SQL Server (12.0).
Estimated Subtree Cost on SQL Server is 0.325 while on Azure SQL it is 1.431
Azure SQL (84%) and SQL Server (52%)
Plan is same in both the instances.Total plan cost always rounds upto 100%.So you may see one operator having high cost compared to another,but all summing upto 100%.
I am not saying keylookups are bad,but those are Random reads .From your plan i could see a single table was accessed twice (seek and lookup).So i recommend adding altering below index after testing
[IX_InstantMessageThreadAccesses_ProfileId] should have one more key column( archived) and include this column (kastreadon).By this way you will be to avoid nearly 44% of total query cost and it will result SQL in choosing a new plan.
Further i could see your statistics are not to update.I recommend doing an update stats for all the tables with fullscan(this may cause huge I/O activity if the tables are very big)...
UPDATE STATISTICS <<tablename>> WITH FULLSCAN
Update question if you have any questions further with steps done now and any diefferences you are seeing