I have run into this frustrating problem many times!!! If you don't want to purchase a digital signature from Thawte or Verisign then your only other option is to use the selfcert tool from microsoft:
When you create a dig sig using the selfcert tool you can then add it to a VBA project by selecting that signature in the VBA editor under the Tools menu.
When a user opens your application, the security warning they see depends upon their security settings for that application. If their security is set to 'medium' then they see a warning that asks them to disable or enable macros (both disable and enable buttons are enabled). (VBA code is treated as macros by the security features of Office) There will also be an unchecked check box that says 'always trust macros from this source'. If the user checks the box and then clicks 'enable', they will never again be prompted with a security warning for that application.
If the user's security settings for the application are set to 'high', then the 'enable macros' button is disabled and in order to enable the 'enable macros' button they must first check the box. Again, from then on the user won't be prompted with a security warning for that applications again.
When Office is installed, the default security setting for Word is HIGH and for Excel is MEDIUM. Word can really give you problems becuase many users don't bother to read the security warning and don't understand that they first need to click the check box and then click the 'enable macros' button. It's even worse if you have added VBA code to a Word document and don't sign it at all because if the user's security setting is 'HIGH' (the default) the doc will open with no security warning in design mode with all code disabled. So you HAVE to sign Word automation apps.
The only way to change the security setting for an Office application is from the Visual Basic toolbar which isn't visible unless the user right clicks in the toolbar area and selects it. You can't change the user's security settings via code in your project because that would obviously defeat the purpose of preventing malicious code from running.
So your best bet is to send an email to all the users of your app and tell them how to accept your signature the first time they run your application otherwise they won't figure it out - trust me I been through this many times. Also, when you use the self cert tool to sign your project the security warning will state that the publisher (i.e., you) hasn't been authenticated and shouldn't be trusted so make sure when you create the signature using the selfcert tool you include your name and the company name (there is only one input line so you will have to combine them) so users will have some level of comfort. When you self sign a project, I think the security warning looks much worse from a 'creating fear in the user' standpoint than unsigned projects. From the programmers standpoint this is frustration because you know your code is safe, but from Microsoft's standpoint they don't know you or your intentions. But again if you can get your users to accept your signature, they won't see any more security warnings.
Really a dig sig from Thawte (they're cheaper) or Verisign is the best solution, but they are expensive and require a yearly fee and you can't just call them up and request a signature - you have to go through a process and verify your company and your validity to them. If you happen to work for a software company someone in your company already probably has a authenticated signature your could use.
Sorry for the long reply, but I have felt your pain before. It's hard enough getting your code to work right across multiple machines and OS versions without having to deal with the security issues.