Все запросы, которые будут использоваться на большинстве страниц, лучше делать в базовом контроллере.
Для меню, в вашем случае лучше использовать шаблонизатор. Например
файл: main.blade.php
<html>
<body>
@yield('menu')
@yield('content')
</body>
</html>
Файл page.blade.php
@extends('main')
@section('menu')
@include('categories', ['categories'=>$categories])
@stop
@section('content')
<div>Content</div>
@stop
файл categories.blade.php
<ul>
@foreach($categories as $category)
<li>{{$category->name}}</li>
@endforeach
</ul>
А в контроллере запрашивать
return View::make('page',['categories'=>$this->categories()]);
Так вы сможете подключать меню когда вам нужно, просто создавая в шаблоне секцию 'menu'