Так вопрос, если их украли, несут ли за это ответственность они?

Здравствуйте.

Да, конечно, хостел несет персональную имущественную ответственность перед Вами, поскольку в данном случае Вами (невольно) был заключен договор безвозмездного хранения Ваших кроссовок. 

При этом этот договор, помимо прочего, был Вам навязан, что также является незаконным.

Вы можете требовать возмещения убытков. При этом за помощью также можете обратиться в Роспотребнадзор и Прокуратуру.

Если не поможет — в суд.

Удачи.

Доброго времени суток! 

В Вашем случае читаем Гражданский кодекс, статью 925. Хранение в гостинице.

1. Гостиница отвечает как хранитель и без особого о том соглашения с проживающим в ней лицом (постояльцем) за утрату, недостачу или повреждение его вещей, внесенных в гостиницу, за исключением денег, иных валютных ценностей, ценных бумаг и других драгоценных вещей.
Внесенной в гостиницу считается вещь, вверенная работникам гостиницы, либо вещь, помещенная в гостиничном номере или ином предназначенном для этого месте.
2. Гостиница отвечает за утрату денег, иных валютных ценностей, ценных бумаг и других драгоценных вещей постояльца при условии, если они были приняты гостиницей на хранение либо были помещены постояльцем в предоставленный ему гостиницей индивидуальный сейф независимо от того, находится этот сейф в его номере или в ином помещении гостиницы. Гостиница освобождается от ответственности за несохранность содержимого такого сейфа, если докажет, что по условиям хранения доступ кого-либо к сейфу без ведома постояльца был невозможен либо стал возможным вследствие непреодолимой силы.
3. Постоялец, обнаруживший утрату, недостачу или повреждение своих вещей, обязан без промедления заявить об этом администрации гостиницы. В противном случае гостиница освобождается от ответственности за несохранность вещей.
4. Сделанное гостиницей объявление о том, что она не принимает на себя ответственности за несохранность вещей постояльцев, не освобождает ее от ответственности.
5. Правила настоящей статьи соответственно применяются в отношении хранения вещей граждан в мотелях, домах отдыха, пансионатах, санаториях, банях и других подобных организациях.

Итог -  объявление о том, что хостел не несёт ответственности — ничтожно.

Удачи!