You would have done well to have taken a few deep breaths and calmly considered the clear advice given by Corion in Re^2: Replacing duplicate string (and also lostjimmy's pseudocode), but since others have given detailed replies, so shall I.

You don't say how the data is held (In a scalar? An array of lines? In an unopened file?), but you and others are going with processing a file line-by-line, which generalizes nicely to processing an array, so I'll take that approach.

use warnings;
use strict;

my $bol_priority = qr{ \A priority }xms;  # 'priority' begins a line
my $blank_line   = qr{ \A \s* \z   }xms;

my $saw_priority = '';

while (<DATA>) {

    s{ $bol_priority }{bandwidth}xms if $saw_priority;

    $saw_priority = /$bol_priority/ .. /$blank_line/;

    print;

    }

__DATA__
Class control
priority 5
Class voip
priority 30
Class video
priority 40


Class control
priority 10
Class voip
priority 25
Class video
priority 45
[download]

Output:

Class control
priority 5
Class voip
bandwidth 30
Class video
bandwidth 40


Class control
priority 10
Class voip
bandwidth 25
Class video
bandwidth 45
[download]

Update: Added reference to lostjimmy's reply.