It depends. If the FK column is used in the queries, I'd combine them. If it's not, then it won't help you.

You do want an index with the FK column as the first column. This will speed up queries that join the parent and child tables. If it's a query like

select col

from menu m

inner join submenu s

on m.menuid = s.menuid

where mnu_order = @x

then combining these makes sense. However if you are querying the menu_order without the FK at times, then this isn't necessarily going to help. You might need separate indexes that cover separate queries.

Menus typically don't have lots of rows, meanings tens, hundreds of thousands or millions. If these tables are relatively small, < 1000 rows, I'm not sure you're going to get much benefit from spending too much time indexing.