my try for a working helper spec with devise and cancan. all tests pass but I'm still not happy about it. My worries are in the comments! --> changed from revision 3 to 7 to a shared_example and matcher usage. Revision 8 groups the shared examples together. Wording now better.

application_helper.rb

module ApplicationHelper

  def link_to_sprite(sprite_class, url_or_object, options={})
    link_to url_or_object, options do
      content_tag :i, :class => sprite_class do end
    end
  end

def render_button(obj, right, display, url_or_object, options={})
    if can? right, obj
      css_class = "btn"
      if defined? options[:primary] and options[:primary]
        css_class << " btn-primary"
      end
      if right == :destroy
        css_class << " btn-danger"
        options[:method] = :delete
        options[:confirm] = "Are you sure?"
        # is added for tests!!!
        options[:id] = "delete_#{obj.class.name.downcase}_#{obj.id}"
      end
      options[:class] = css_class
      link_to display, url_or_object, options
    end
  end

end

login_support.rb

module ValidUserHelper
  def signed_in_as_a_valid_user
    @user ||= FactoryGirl.create :normal_user, :login => 'user'
    sign_in @user # method from devise:TestHelpers
  end

  def signed_in_as_a_valid_admin_user
    @user ||= FactoryGirl.create :admin_user, :login => 'admin'
    sign_in @user # method from devise:TestHelpers
  end
end

RSpec.configure do |config|
  config.include ValidUserHelper, :type => :controller
  config.include ValidUserHelper, :type => :helper
end

show_delete_operation.rb

RSpec::Matchers.define :show_delete_operation do |expected|

  match do |actual|
   # how to check efficiently if the delete icon is displayed?
   # could only come up with this, but I don't like being dependent on direct html code
    actual.include? "data-method=\"delete\""
    # the id is included when generating html so I can test this specifically
    actual.include? "delete_#{expected.class.name.downcase}_#{expected.id.to_s}"
  end

  failure_message_for_should do |actual|
    "expected to show delete operation"
  end

  failure_message_for_should_not do |actual|
    "expected not to show delete operation"
  end

  description do
    "show delete operation"
  end
end

show_edit_operation.rb

RSpec::Matchers.define :show_edit_operation do |expected|

  match do |actual|
    # don't you just looooove the message concept in Rails? :)
    actual.include? Rails.application.routes.url_helpers.send("edit_#{expected.class.name.downcase}_path", expected)
  end

  failure_message_for_should do |actual|
    "expected to show edit operation"
  end

  failure_message_for_should_not do |actual|
    "expected not to show edit operation"
  end

  description do
    "show edit operation"
  end
end

users_helper.rb

  module UsersHelper

    def user_links(user)
      [
        if can? :update, user
          link_to_sprite('icon-edit', edit_user_path(user), {:title => 'Edit User'})
        end,
        if can? :destroy, user and current_user != user
          link_to_sprite('icon-trash', user_path(user),
                       {
            :confirm => 'Are you sure?',
            :method => :delete,
            :title => 'Delete User'
          })
        end,
      ].compact.join('   ').html_safe
    end
    
    def user_buttons(user)
      [
        if can? :update, user
          render_button(user, :update, "Edit User", edit_user_path(user), :primary => true)
        end,
        if can? :destroy, user and current_user != user
          render_button(user, :destroy, "Delete User", user_path(user))
        end
      ].compact.join(' ').html_safe
    end

  end

users_helper_spec.rb

require 'spec_helper'

describe UsersHelper do
  # these 3 shared_examples will probably be used by all object helper methods
  # where to put?
  # somewhere in support directory?
  shared_examples "show edit operation only" do
    it "displays edit operation" do
      rendered.should show_edit_operation(object)
    end
    it "displays no delete operation" do
      rendered.should_not show_delete_operation(object)
    end
  end

  shared_examples "show no operations" do
    it "displays no edit operation" do
      rendered.should_not show_edit_operation(object)
    end
    it "displays no delete operation" do
      rendered.should_not show_delete_operation(object)
    end
  end

  shared_examples "show all operations" do
    it "displays edit operation" do
      rendered.should show_edit_operation(object)
    end
    it "displays delete operation" do
      rendered.should show_delete_operation(object)
    end
  end

  describe "#user_links" do
    context "logged in as an normal user" do
      before :each do
        #login as normal user
        signed_in_as_a_valid_user
      end

      context "when shown user is not current user" do
        let(:object) {create(:user)}

        context "when generating links" do
          let(:rendered) {helper.user_links(object)}

          it_behaves_like "show no operations"
        end

        context "when generating buttons" do
          let(:rendered) {helper.user_buttons(object)}

          it_behaves_like "show no operations"
        end
      end

      context "when shown user is current user" do
        let(:object) { @user }

        context "when generating links" do
          let(:rendered) {helper.user_links(object)}

          it_behaves_like "show edit operation only"
        end

        context "when generating buttons" do
          let(:rendered) {helper.user_buttons(object)}

          it_behaves_like "show edit operation only"
        end
      end
    end

    context "logged in as an admin user" do
      before :each do
        #login as admin
        signed_in_as_a_valid_admin_user
      end

      context "when shown user is not current user" do
        let(:object) {create(:user)}

        context "when generating links" do
          let(:rendered) {helper.user_links(object)}

          it_behaves_like "show all operations"
        end

        context "when generating buttons" do
          let(:rendered) {helper.user_buttons(object)}

          it_behaves_like "show all operations"
        end
      end

      context "when shown user is batch user (id=1)" do
        let(:object) { user = create(:user)
        user.id = 1
        user}

        context "when generating links" do
          let(:rendered) {helper.user_links(object)}

          it_behaves_like "show no operations"
        end

        context "when generating buttons" do
          let(:rendered) {helper.user_buttons(object)}

          it_behaves_like "show no operations"
        end

      end
    end
  end

end

Sorry again for taking so long to get back to you--I've been on the road for most of the last month.

Regarding your question in show_delete_operations.rb: I usually test against what the outputted string of HTML should look like, but such tests generally don't have to deal with as complex of helpers as what you've got here. My tendency is to handle these in integration specs instead.

I think your shared examples should go into spec/support, maybe even spec/support/examples? AFAIK there's no strict convention for this, but I like the approach you're taking to split them out.