Как сделать бота CallBack API?

Но я так и не могу понять где взять этот сервер, у меня есть на AWS машина на Linux, подойдёт ли она? Как вообще сделать этот сервер,

AWS подойдет.
Если на Python, то для простоты можно сделать на Flask.

По сути это обычный вебсервер, с проектом на %framework_name%.
CallBack url это путь на вашем сервере куда будет прилетать запрос (POST) от ВКонтакте.
И же по этому пути вы обрабатываете, те данные которые присылает ВК.