This is a very interesting and important thread. Some great points from both Ted and Stefan. This is also a very difficult problem, but one we do need to consider and see what we can do to improve the current situation.
I don't think we can automate the process and even our abilities to have functions/libraries which can assist with verifying/checking packages will be limited as I suspect you will need a reasonable high level of understanding of elisp, emacs and security threats in order to use such tools effectively. However, this isn't to say we shouldn't try to improve the situation.
In an ideal world, we would probably have a team of specialists who would review new packages, provide an assessment of their relative security risks and sign the code. This is very unlikely.
A common mistake made in security is to focus too much on the technology and technical solutions to the problem rather than focus on the process and people. In addition to looking at tools/libraries which would help with analysis of code, I think we also need to look at the processes associated with uploading of packages to repositories, retrieving packages from repositories and their installation to identify weaknesses and see what we can do to tighten up those weaknesses. A good example of this is Stefan's other post regarding the org package. In addition to identifying security weaknesses in the process, we need to identify usability weaknesses which result in people doing the wrong thing - either because doing the right thing is too hard or just simply a lack of awareness.
I also think it would be a good idea to see what we can do with respect to improving awareness and understanding of security risks and how to manage them for end users. While there is likely quite a few who will not care, there are some who do and we should try to empower them as much as possible by providing information/documentation on what they can do, what they should look out for, how to assess code security risks etc. This information could also be very useful in identifying what sort of tools might be useful and/or what features they would require.
Something else which might be worth considering would be some way to share analysis results. Knowing that someone has at least tried to look at a package is likely to provide at least some additional confidence over a package - we would need to have some protection against 'false' reviews.
A good starting point might be to either add a section to the manual or on an emacs wiki which covers techniques and approaches that could be used for assessing security implications for a package and how to harden your package.el setup etc. This could even become the start of a requirements gathering for what tools or support libraries are needed to assist in this type of activity.