そういえば自分の中でだいたいパターン化してきるなと思ったので、メモがてら整理しつつ、初心者の人に参考になればと思いつつ、上級者の人には教えてほしい的なものを書いてみます。

Procの詳細については良記事がいくつかあるので省きます。
[Ruby] ブロックとProcをちゃんと理解する
 Procを制する者がRubyを制す（嘘）

1. デザインパターンのテンプレートメソッドパターン

私の場合はRubyを勉強してからすぐにRubyによるデザインパターンを買ったのですが、テンプレートメソッドパターンで使われてるのを見て、初めてProcが便利だなって感覚を持ちました。
詳細は本や他の記事に譲りますが、基本的な概念としては冗長性を削ってよりDRYに、ポータブル化して遅延評価する事で可読性の向上って感じだと思ってます。
というかProcを使う時って全部この概念に則っていると思います。
例えばRailsだと汎用的なaction（import_csv、download_csvみたいな）をライブラリ化しておいて、中の処理の微妙な差異は呼び出す側がProcを渡す事で吸収する、みたいな事は良くやりますよね。

2. ループ内での分岐排除

下記のように毎回分岐が走るのは性能的によろしくないです

status = 0
values.each do |value|
  case status
  when 0
    # valueを使った処理
  when 1
    # valueを使った処理
  when 2
    # valueを使った処理
  end
end

なので以下のように毎回分岐を避けようとしますが、これだとコードが冗長になってしまうケースがたまにあります。eachとか3回も書いてますし。

case status
when 0
  values.each do |value|
    # valueを使った処理
  end
when 1
  values.each do |value|
    # valueを使った処理
  end
when 2
  values.each do |value|
    # valueを使った処理
  end
end

こういう時にProcを使うとすっきりします。
callback的な事ですよね。

case status
when 0
  block = -> (value) {
    # valueを使った処理
  }
when 1
  block = -> (value) {
    # valueを使った処理
  }
when 2
  block = -> (value) {
    # valueを使った処理
  }
end

values.each do |value|
  block.call(value)
end

もっとも、上記パターンを応用した下記のようなパターンを使うシチュエーションの方が多いように思います。

hash = {}
hash[0] = -> (value) { 処理 }
hash[1] = -> (value) { 処理 }
hash[2] = -> (value) { 処理 }

values.each do |value|
  hash[value.status].call(value)
end

ただし、このやり方には個人的に一つわかってない事があります。
それは、GCです。
ブロック内でメモリ消費量の多いオブジェクト生成をして、大量ループが走ったらどうなるんだろうってのが良くわかってないんですよね。
そういうシチュエーションに出くわした事がなく、調べずに来てしまっています（ひどい言い訳）。
GCがやたら非効率になるような事がなければいいのですが。

3. いわゆるクロージャ

詳細はこの記事に託します。
http://www.atmarkit.co.jp/ait/articles/1409/29/news035_3.html

4. かっこつけたい時

こういうの書いたらドヤっていいと思うんです。

[1, 2, 3].map(&:my_method)

[関連]メソッド内でyieldを使うか.callを使うか

Procの使いどころは以上なんですけど、yieldの使いどころもパターン化してきてるのでついでに書いてみます。

yieldを使う時、それはEnumerator のインスタンスを返したいケースがある時です。
つまり、こんなスタイルになります。

def method
  if block_given?
    yield
  else
    to_enum
  end
end

既存ライブラリをモンキーパッチしたり、オレオレライブラリを作る時とか、基本的にビジネスロジックに超無関心な所で使う感じがあります。
逆にto_enumしないようなケースでは.callするようにしてます。

def method(proc)
  proc.call
end

理由は可読性です。
Rubyに慣れ親しんでないと前者の書き方は違和感しかないと思います。
後者はまだオブジェクトを扱っている感がありますし、少しProcについて勉強するだけでしっくりくるようになると思うわけです。
あと、後者の場合&をつけてブロックを受け取る方法もありますが、あまり好きじゃないんですよね。
ブロックを渡された事が明示的になるメリットはありますが、これも慣れ親しんでないと違和感が大きいですし、いろんな書き方があると混乱を招きそうで。
blockを受け取ってyieldするか、
procを受け取って.callするか
のどっちかに倒した方がいいと個人的には思ってます。
以上です。

Procの使いどころとか

1. デザインパターンのテンプレートメソッドパターン

2. ループ内での分岐排除

3. いわゆるクロージャ

4. かっこつけたい時

[関連]メソッド内でyieldを使うか.callを使うか