The problem is when you create a menu item in Excel, you add it to your app profile, not the workbook (it is possible to attach toolbars to a workbook, but when you close the workbook, the toolbar remains). This is why to effectively distribute code, it's best to deploy an addin to users that they copy to their XLSTART directory so it will load when Excel starts (or they can place it in their profile's Addins directory and enable it through Tools>AddIns).
You can then use the Workbook Open and close event to build/delete the menu.
Here's the code and a mini-tutorial:
In the VBE, go to the "ThisWorkbook" code pane and select those events using the dropdown menus above it. The basic framework for menu code in the ThisWorkBook module looks like this[VBA]Option Explicit

Private Sub Workbook_Open()
DeleteMenu 'delete any exitsing menus
BuildMenu 'create new menu
End Sub

Private Sub Workbook_BeforeClose(Cancel As Boolean)
DeleteMenu
End Sub

Private Sub BuildMenu()

Dim cb As CommandBarControl
Dim cbItem As CommandBarButton

With Application.CommandBars("Worksheet Menu Bar") 'with the main menu bar
Set cb = .Controls.Add(msoControlPopup) 'add a menu
With cb 'with the nem menu
.Caption = "New Menu" 'set the caption

Set cbItem = .Controls.Add(msoControlButton) 'add a new item
With cbItem
.Caption = "New Item" 'set its caption
.OnAction = "TestMacro" 'set the marco to run from it
End With

Set cbItem = .Controls.Add(msoControlButton) 'add another item
With cbItem
.Caption = "New Item 2" 'set its caption
.OnAction = "TestMacro2" 'etc

End With
End With
End With

End Sub

Private Sub DeleteMenu()

Dim cb As CommandBarControl
'deletes all the menus in the main menu bar called "New Menu"
For Each cb In Application.CommandBars("Worksheet Menu Bar").Controls
If cb.Caption = "New Menu" Then cb.Delete
Next
End Sub[/VBA]The action commands are the macros you are calling, for this example, add a standard module and insert the following[VBA]Option Explicit

Sub TestMacro()
'add code for action here
MsgBox "This is a test"
End Sub

Sub TestMacro2()
'add code for action here
MsgBox "This is another test"
End Sub[/VBA]Now you can go back to Excel and save the workbook as an AddIn (.XLA). The dialog should go to your default AddIns directory, so save it there. You can now select it in Tools>AddIns to set it to load when Excel starts.

PowerPoint works in a similar way but does not have presentation events (they can be enabled by creating an event class, but thats another story).
So to get code to fire when opening and closing a presentation, create two routines in a standard module named "Auto_Open" and "Auto_Close". The rest of the code is identical so for this example, you have a single standard module that looks like this[VBA]Option Explicit

Sub Auto_Open()
BuildToolBar
End Sub

Sub Auto_Close()
DeleteToolbar
End Sub

Sub BuildToolBar()
Dim cb As CommandBarControl
Dim cbItem As CommandBarButton

With Application.CommandBars("Menu Bar")
Set cb = .Controls.Add(msoControlPopup)
With cb
.Caption = "New Menu"
Set cbItem = .Controls.Add(msoControlButton)
cbItem.Caption = "New Item"
cbItem.OnAction = "TestMacro"
End With
End With
End Sub

Sub DeleteToolbar()
Dim cb As CommandBarControl

For Each cb In Application.CommandBars("Menu Bar").Controls
If cb.Caption = "New Menu" Then cb.Delete
Next
End Sub

Sub TestMacro()
'add code for action here
MsgBox "This is a test"
End Sub[/VBA]Once your happy with the result, save the PPT (this is the original you can work on) then, for distribution save a copy as a .PPA. As with Excel, the dialog should go to your default AddIns directory. You can now select it in Tools>AddIns to set it to load when PowerPoint starts.

That deals with the basics. Hopefully I've explained it clearly - its worth also seaching MSDN for more detail