Where have "predefined SMS messages" gone in Android 5?
You should look in the Phone/Dialer app, not SMS/Hangout app. This is from stock Nexus 6 Lollipop:


Open the Phone app


Tap the overflow menu besides the search box and tap "Settings": 


Tap "General"


Tap "Quick Responses":


Edit your quick responses editing the text box that pops up when you tap on the list view: