Switch from while loop to for loop:

for (( p=1; p<=$#; p++)); do
    printf '#%u: %q\n' $p "${!p}"
done

I use format %q in my example to show escapes user friendly.

How can I get the #1 to shift as well?

A counter is mostly used while looping through the positional parameters, something like this.

#!/usr/bin/env bash

echo "You have entered $# arguments:"

n=1
while (($#)); do
  printf '#%d: %s\n' "$((n++))" "$1"
  shift
done

I would rewrite it in a for loop, without the shift

#!/usr/bin/env bash

echo "You have entered $# arguments:"

n=1
for arg; do
  printf '#%d: %s\n' "$((n++))" "$arg"
done

With indirect expansion like @Wiimm did with a C-style for loop, something like

while ((n++<$#)); do
  printf '#%d: %q\n' "$n" "${!n}"
done

• See Arithmetic Expansion

  env LESS= MANPAGER="less --pattern='^\\s+Arithmetic\ Expansion$'" man bash

• See Arithmetic Evaluation

  env LESS= MANPAGER="less --pattern='^arithmetic\ evaluation$'" man bash

• Indirect expansion is in Parameter Expansion if the first character of parameter is an exclamation point (!)

  PAGER="less +/If\ the\ first\ character\ of\ parameter\ is\ an\ exclamation\ point" man bash

An approach with the fewest modifications to your original attempt could be saving the number of arguments before the loop, then count inside the loop by subtracting from it the modified count (increase by 1 to make it 1-based):

#!/bin/bash

echo "You have entered $# arguments:"

n=$#
while (($#));

do
  echo "$((n-$#+1)): $1"
  shift
done

Why do you need the shift?

As mentioned elsewhere, a counter is the usual solution. If shift isn't required for some other reason you didn't include, here's another for loop implementation.

$: set one two three; declare -i i=0; for o in "$@"; do i+=1; echo "#$i: $o"; done
#1: one
#2: two
#3: three

And of course, as Jetchisel demonstrated, if you're using the default arguments you can just skip the in "$@" bit...

$: set one two three; declare -i i=0; for o; do i+=1; echo "#$i: $o"; done
#1: one
#2: two
#3: three

If you do require the shift, and/or prefer the while -

$: set one two three; declare -i i=0; while(($#)); do i+=1; echo "#$i: $1"; shift; done
#1: one
#2: two
#3: three

Make sure you declare that counter as an integer, or you'll have to take other steps to get the result you want...

$: set one two three; i=0; while(($#)); do i+=1; echo "#$i: $1"; shift; done # oops!
#01: one
#011: two
#0111: three

$: set one two three; i=0; while(($# && ++i)); do echo "#$i: $1"; shift; done # corrected
#1: one
#2: two
#3: three

There are a million ways to do this.
Here's a less efficient one just for the fun of it. :)

$: seq $# | while read -r i; do echo "#$i: ${!i}"; done
#1: one
#2: two
#3: three

Playing with array witout loop

The goal is to dump array by shifting indexes by 1.

Option 1

Using recent bash, you could avoid (slow) bash loop, for array manipulation:

#!/usr/bin/env bash

arry=("$@")
declare -ai idx=(${!arry[@]})
idx=( " ${idx[@]/%/ + 1 } " )
printf -v tmpStr '%d: %%s\\n' ${idx[@]}
printf "$tmpStr" "${arry[@]}"

Then

./args.sh foo bar baz "foo bar" 

1: foo
2: bar
3: baz
4: foo bar

Option 2

#!/usr/bin/env bash

cnt=0
printf -v str '%*s' $# ''
declare -ai arry=(${str// /++cnt })
printf -v str '%s: %%q\\n' "${arry[@]}"
printf "$str" "$@"

Then

./args.sh foo bar baz "foo bar" 

1: foo
2: bar
3: baz
4: foo bar

Have a look at Converting a Bash array into a delimited string

The only reason to use Bash is because Perl is not installed. You need a loop counter. You can use a C style for loop with a built in counter like so...

#!/usr/bin/perl -w

for($i=0;$i<@ARGV;$i++){
  print $i+1 . ": $ARGV[$i]\n";
}

You could use a Perl style foreach loop like so...

#!/usr/bin/perl -w

$i=1;
for(@ARGV){ #you can use "for" instead of "foreach" Perl will figure it out for you
  print "$i: " . $_ . "\n";
  $i++;
}

You don't have to specify an iterator for a foreach loop, the $_ variable will contain the array value for each iteration. If you want the index of that value however, you will have to manually keep a counter. As in a while loop.

And finally, you can use a foreach loop with the .. operator. The .. operator will populate a list of the numbers in increasing order. This is useful when you need to work with the array index as well as the value. And the size of all arrays can be found with the $#array syntax, so something like this would work as well...

#!/usr/bin/perl -w

for(0..$#ARGV){
  print $_+1 . ": $ARGV[$_]\n";
}

All three match your expected output...

$ perl loop.counter.pl one two three

1: one
2: two
3: three

Golfed at 41 characters...

$ perl -le 'print $_+1 . ": $ARGV[$_]" for(0..$#ARGV)' one two three